Independent set in k-claw-free graphs: conditional -boundedness and the power of LP/SDP relaxations

DOI10.1007/978-3-031-49815-2_15MaRDI QIDQ6574949zbMATH OpenFDO

Authors Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Joachim Spoerhase

Publication date 19 July 2024

zbMATH Keywords

convex relaxationRamsey theory\( \chi \)-boundedness

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 1617260 (Why is no real title available?)
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 1947059 (Why is no real title available?)
• scientific article; zbMATH DE number 1757962 (Why is no real title available?)
• scientific article; zbMATH DE number 6297805 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A characterization of perfect graphs
• A note on fractional coloring and the integrality gap of LP for maximum weight independent set
• A survey of \(\chi\)-boundedness
• An improved approximation for maximum weighted \(k\)-set packing
• Approximation algorithms for maximum independent set of pseudo-disks
• Claw-free graphs. VI: Colouring
• Coloring and Maximum Weight Independent Set of Rectangles
• Efficient bounds for the stable set, vertex cover and set packing problems
• Global optimization with polynomials and the problem of moments
• Greedy local improvement and weighted set packing approximation
• Inapproximability of vertex cover and independent set in bounded degree graphs
• Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
• Maximum independent set of rectangles
• On the Lovász theta function for independent sets in sparse graphs
• On the complexity of approximating \(k\)-set packing
• Semialgebraic Proofs and Efficient Algorithm Design
• Semidefinite programming relaxations for semialgebraic problems
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The early evolution of the \(H\)-free process
• The triangle-free process

Cited in

(1)

• Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations

This page was built for publication: Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6574949)