On connection between bicliques of hypergraph and all maximally complete submatrices of adjacency matrix | Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika – Tomsk State University Journal of Control and Computer Science. 2021. № 56. DOI: 10.17223/19988605/56/10

On connection between bicliques of hypergraph and all maximally complete submatrices of adjacency matrix

The connection between the problem of finding all maximally complete submatrices of the (0, 1) -matrix and the problem of finding all maximal bicliks of hypergraphs is investigated. The HFindMCS algorithm for finding all maximally complete submatrices of the (0, 1) -matrix is developed. The theoretical analysis of the computational complexity of the proposed algorithm is carried out and its correctness is proved. Computational experiments have shown the effectiveness of the HFindMCS algorithm on hypergraphs with limited degree. A procedure is proposed for the transition from solving the problem of finding all maximally complete submatrices of the (0, 1) -matrix to solving the problem of finding all maximal biclips of hypergraphs.

Download file

Counter downloads: 57

Keywords

hypergraph, maximal bicliques, (0, 1)-matrix, maximally complete submatrices

Authors

Name	Organization	E-mail
Soldatenko Aleksandr A.	Siberian Federal University	asoldatenko@sfu-kras.ru
Semenova Darya V.	Siberian Federal University	dvsemenova@sfu-kras.ru

Всего: 2

References

Мейер Д. Теория реляционных баз данных. М. : Мир, 1987. 608 с.

Konstantinova E.V., Skorobogatov V.A. Application of hypergraph theory in chemistry // Discrete Mathematics, 2001. V. 235, is. 1-3. P. 365-383.

Graham R.L., Pollak H.O. On the addressing problem for loop switching // The Bell System Technical Journal. 1971. V. 50, № 8. P. 2495-2519.

Попов В.Б. Экстремальная нумерация вершин гиперграфа и задача объектно-признаковой кластеризации // Динамические системы. 2010. № 28. С. 99-112.

Ganter B., Wille R. Formal concept analysis. Springer, 1999. 284 p.

Kuznetsov S., Obiedkov S. Comparing performance of algorithms for generating concept lattices // J. Exp. Theor. Artif. Intell. 2002. V. 14. P. 189-216.

Блюмин С.Л. Полные гиперграфы. Спектры лапласианов. Мультиагентные системы // Управление большими системами, 2010. № 30. С. 5-23.

Тараканов В.Е. Комбинаторные задачи и (0, 1)-матрицы. М. : Наука, 1985. 195 с.

Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы: общий подход. М. : БИНОМ. Лаборатория знаний, 2009. 406 с.

Маркус М., Минк Х. Обзор по теории матриц и матричных неравенств. М. : Наука, 1972. 232 с.

Beineke L., Wilson R.J. Topics in Algebraic Graph Theory. Cambridge ; New York : Cambridge University Press, 2008. 276 p. (Mathematical Sciences Faculty Publications).

Jukna S., Kulikov A. On covering graphs by complete bipartite subgraphs // Discrete Mathematics. 2009. V. 309. P. 3399-3403.

Faure N., Chretienne P., Gourdin E., Sourd F. Biclique completion problems for multicast network design // Discrete Optimization. 2007. V. 4, is. 3-4. P. 360-377.

Hermelin D., Manoussakis G. Efficient enumeration of maximal induced bicliques // Discrete Applied Mathematics. 2020. DOI: 10.1016/j.dam.2020.04.034

Shaham E., Yu H., Li X. On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach // Proc. of the 2016 SIAM International Conference on Data Mining (SDM). 2016. P. 315-323.

Damaschke P. Enumerating maximal bicliques in bipartite graphs with favorable degree sequences // Inf. Process. Lett. 2014. V. 114, is. 6. P. 317-321.

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. : Мир, 1982. 416 с.

Кофман А. Введение в прикладную комбинаторику. М. : Наука, 1975. 480 с.

Bretto A. Hypergraph theory: an introduction. Springer, 2013. 119 p.

Zverovich I., Zverovich I. Bipartite bihypergraphs: A survey and new results // Discrete Mathematics. 2006. V. 306. P. 801-811.

Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М. : Наука, 1990. 384 с.

Харари Ф. Теория графов. М. : URSS, 2018. 304 с.

Prisner E. Bicliques in graphs I: bounds on their number // Combinatorica. 2000. V. 20. P.109-117.

Lyu B., Qin L., Lin X., Zhang Y., Qian Z., Zhou J. Maximum biclique search at billion scale // Proc. VLDB Endow. 2020. P. 1359-1372.

Alexe G., Alexe S., Crama Y., Foldes S., Hammer P.L., Simeone B. Consensus algorithms for the generation of all maximal bicliques // Discrete Applied Mathematics. 2004. V. 145. P. 11-21.

Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 3-е изд. М. : Вильямс, 2013. 1328 с