Using critical sets to solve the maximum independent set problem

✍ Scribed by Sergiy Butenko; Svyatoslav Trukhanov

• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 139 KB
• Volume: 35
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2006.07.004

✦ Synopsis

A method that utilizes the polynomially solvable critical independent set problem for solving the maximum independent set problem on graphs with a nonempty critical independent set is developed. The effectiveness of the proposed approach on large graphs with large independence number is demonstrated through extensive numerical experiments.