Approximating independent sets in sparse graphs

DOI10.1137/1.9781611973730.1MaRDI QIDQ5363078zbMATH OpenOpenAlexFDO

Authors N. Bansal

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.1

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• On the Lovász theta function for independent sets in sparse graphs
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• scientific article; zbMATH DE number 1003268
• SDP-based algorithms for maximum independent set problems on hypergraphs
• SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs

Cited in

(18)

• Computing independent sets in graphs with large girth
• On approximation properties of the independent set problem for low degree graphs
• Approximating weighted neighborhood independent sets
• Sparse hypergraphs with low independence number
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Efficient independent set approximation in unit disk graphs
• Fair splittings by independent sets in sparse graphs
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Approximation algorithms for independent sets in map graphs
• On the Lovász theta function for independent sets in sparse graphs
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• Bilu-Linial stability, certified algorithms and the independent set problem
• Simple and local independent set approximation
• A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
• Greedy approximations of independent sets in low degree graphs

This page was built for publication: Approximating independent sets in sparse graphs

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