Algorithm for finding maximum independent set

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.