Using critical sets to solve the maximum independent set problem

DOI10.1016/j.orl.2006.07.004zbMath1149.90375OpenAlexW2103112216MaRDI QIDQ2457270

Svyatoslav Trukhanov, Sergiy I. Butenko

Publication date: 30 October 2007

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2006.07.004

zbMATH Keywords

critical setMaximum independent setlarge-scale discrete optimization

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Integer programming (90C10)

Related Items (11)

On some conjectures concerning critical independent sets of a graph ⋮ Critical sets, crowns and local maximum independent sets ⋮ Finding near-optimal independent sets at scale ⋮ Critical and maximum independent sets of a graph ⋮ Critical independent sets and König-Egerváry graphs ⋮ The critical independence number and an independence decomposition ⋮ A polytime preprocess algorithm for the maximum independent set problem ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ Simple and fast surrogate constraint heuristics for the maximum independent set problem ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ Monotonic properties of collections of maximum independent sets of a graph

Uses Software

• DIMACS

Cites Work

• Test case generators and computational results for the maximum clique problem
• Vertex packings: Structural properties and algorithms
• On Finding Critical Independent and Vertex Sets
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
• A Selection Problem of Shared Fixed Costs and Network Flows
• Notes—On a Selection Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Using critical sets to solve the maximum independent set problem