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

abstract

  • 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.

published proceedings

  • Operations Research Letters

author list (cited authors)

  • Butenko, S., & Trukhanov, S.

citation count

  • 15

complete list of authors

  • Butenko, S||Trukhanov, S

publication date

  • July 2007