Using critical sets to solve the maximum independent set problem

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.

authors

• Butenko, Sergiy

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

published in

• Operations Research Letters  Journal

Digital Object Identifier (DOI)

• 10.1016/j.orl.2006.07.004

start page

• 519

end page

• 524

volume

• 35

issue

• 4