Ramsey theory and integrality gap for the independent set problem

DOI10.1016/j.orl.2014.01.007zbMath1408.05087OpenAlexW2035383060MaRDI QIDQ1667206

Robert D. Carr, Giuseppe Lancia

Publication date: 27 August 2018

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

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

zbMATH Keywords

Ramsey theoryintegrality gapindependent set problemILP formulations

Mathematics Subject Classification ID

Integer programming (90C10) Generalized Ramsey theory (05C55) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• An exact algorithm for the maximum clique problem
• Finding a Maximum Clique in an Arbitrary Graph
• Vertex packings: Structural properties and algorithms
• Approximating Maximum Clique by Removing Subgraphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Unnamed Item
• Unnamed Item
• Unnamed Item