Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: Springer Science and Business Media Deutschland GmbH; 20 September 2021 through 24 September 2021; 20 September 2021 through 24 September 2021
Год издания: 2022
Идентификатор DOI: 10.1007/978-3-030-97110-6_10
Ключевые слова: hypergraph, maximal induced bicliques, search algorithm
Аннотация: The problem of finding all maximal induced hypergraph bicliques is considered. The maximal bicliques have many applications and are most in demand in genetic and telecommunication networks. In a hypergraph, an edge can be a subset of any cardinality, and not just a two-element subset of a finite set of vertices. This generalizationПоказать полностьюopens up additional computational capabilities for the hypergraph model applications. The paper considers the relationship between finding the most complete submatrices of the (0, 1)-matrix and finding all the maximum induced bicliques of the hypergraph. The main idea of the hypergraph approach is to use the properties of the hypergraph to efficiently generate solutions for the problems mentioned above. A new algorithm for finding all maximal induced hypergraph bicliques is proposed. The scheme and pseudocode of the proposed algorithm are presented together with a detailed description of its operation. A lemma is proposed that can be used to improve the performance of the algorithm on a special kind of hypergraphs. Results of computational experiments are introduced. © 2022, Springer Nature Switzerland AG.
Журнал: Communications in Computer and Information Science
Выпуск журнала: Vol. 1552 CCIS
Номера страниц: 136-147
ISSN журнала: 00274029