This article is cited in 2 papers

Applied mathematics

Finding all maximal independent sets of an undirected graph

O. S. Firyulina

Saint-Petersburg State University

Abstract: An algorithm of search for all maximal independent sets in an undirected graph is presented. This problem is a so-called NP-complete problem which means the current lack of algorithms for solving it in polynomial time. The proposed algorithm, though also not being a polynomial one, in the worst cases finds a solution faster than the trivial exhaustive algorithm. Comparison of the suggested algorithm with the known Bron–Kerbosch algorithm over a certain set of random generated graphs with different density values is made. Special attention is paid to the comparison over sparse graphs. Bibliogr. 6.

Keywords: maximal independent set, sparse graph, branch and bound method.

UDC: 519.157+519.161+519.163


Accepted: October 25, 2012