Using critical sets to solve the maximum independent set problem Academic Article uri icon


  • 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. © 2006 Elsevier B.V. All rights reserved.

author list (cited authors)

  • Butenko, S., & Trukhanov, S.

citation count

  • 11

publication date

  • July 2007