Recoverable Values for Independent Sets

DOI10.1007/978-3-642-22006-7_41zbMath1334.68087arXiv1103.5609OpenAlexW2057440575MaRDI QIDQ3012827

Daniel Reichman, Uriel Feige

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

zbMATH Keywords

heuristicsindependent setapproximation algorithms

Mathematics Subject Classification ID

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

New bounds for contagious sets, On percolation and ‐hardness, Recoverable Values for Independent Sets, Infinite and Giant Components in the Layers Percolation Model, On giant components and treewidth in the layers model

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