Using critical sets to solve the maximum independent set problem |
| |
| Authors: | Sergiy Butenko Svyatoslav Trukhanov |
| |
| Institution: | Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas, USA |
| |
| 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: | Maximum independent set Critical set Large-scale discrete optimization |
| 本文献已被 ScienceDirect 等数据库收录！ |
