On the Lovász Theta function for Independent Sets in Sparse Graphs

DOI10.1145/2746539.2746607zbMath1321.05176arXiv1504.04767OpenAlexW2034163095MaRDI QIDQ2941507

Anupam Gupta, Nikhil Bansal, Guru Prashanth Guruganesh

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.04767

zbMATH Keywords

semidefinite programmingRamsey theoryindependent setapproximation algorithmslift/project hierarchies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Generalized Ramsey theory (05C55) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

The list chromatic number of graphs with small clique number, Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014., On the Lovász Theta Function for Independent Sets in Sparse Graphs, Unnamed Item, Unnamed Item, New tools and connections for exponential-time approximation, Simple and local independent set approximation

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming