Article ID Journal Published Year Pages File Type
1143097 Operations Research Letters 2007 6 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Using critical sets to solve the maximum independent set problem
Authors
, ,