Finding all maximal independent sets of an undirected graph

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.