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

DOI10.1007/978-3-031-49815-2_15MaRDI QIDQ6574949FDOQ6574949

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

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

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)