This article is cited in 1 paper

Applied mathematics

Algorithm for finding maximum independent set

I. V. Olemskoy, O. S. Firyulina

St. Petersburg State University, 199034, St. Petersburg, Russia Federation

Abstract: The article presents an algorithm MaxIS for finding maximum independent set in an undirected graph. 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, finds a solution faster than the trivial exhaustive algorithm. Each branch of the search tree built by the algorithm MaxIS corresponds to the unique maximal independent set. Results of a comparison of the proposed algorithm with an Robson algorithm, which is now considered one of the best algorithms for the solution of the above problem, are presented. Testing of algorithms have been conducted on some set of arbitrary graphs with different densities. Bibliogr. 6. Il. 4.

Keywords: extremal graph theory, maximum independent set, branch and bound method.

UDC: 519.157+519.161+519.163

Received: October 31, 2013