Recoverable Values for Independent Sets
DOI10.1007/978-3-642-22006-7_41zbMath1334.68087arXiv1103.5609OpenAlexW2057440575MaRDI QIDQ3012827
Publication date: 6 July 2011
Published in: Random Structures & Algorithms, Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.5609
Discrete location and assignment (90B80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20) Vertex degrees (05C07)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- New bounds for contagious sets
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Efficient bounds for the stable set, vertex cover and set packing problems
- Large induced degenerate subgraphs
- On approximation properties of the independent set problem for low degree graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Lower bounds on the independence number in terms of the degrees
- A note on greedy algorithms for the maximum weighted independent set problem
- PASS approximation: a framework for analyzing and designing heuristics
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Recoverable Values for Independent Sets
- On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
- Vertex packings: Structural properties and algorithms
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Structural Information and Communication Complexity
