Greed is good: approximating independent sets in sparse and bounded-degree graphs
DOI10.1145/195058.195221zbMATH Open1344.68286OpenAlexW2075648490MaRDI QIDQ2817635FDOQ2817635
Authors: Magnús M. Halldórsson, Jaikumar Radhakrishnan 
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195221
Recommendations
Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)
Cited In (22)
- The \textsc{max quasi-independent set} problem
- Minimum entropy combinatorial optimization problems
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- Brief announcement: Simple and local independent set approximation
- Independent sets in bounded-degree hypergraphs
- Title not available (Why is that?)
- Ultimate greedy approximation of independent sets in subcubic graphs
- It is hard to know when greedy is good for finding independent sets
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
- Independent Sets in Bounded-Degree Hypergraphs
- Independent sets in graphs with triangles
- Improved approximations for maximum independent set via approximation chains
- The greedier the better: an efficient algorithm for approximating maximum independent set
- Ultimate greedy approximation of independent sets in subcubic graphs
- Greedy approximations of independent sets in low degree graphs
- Derandomized graph products
- Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
- Analysis of greedy algorithms on graphs with bounded degrees
- Stackelberg strategies on epidemic containment games
- On approximation properties of the Independent set problem for degree 3 graphs
- Greed is good for deterministic scale-free networks
- Improved approximations of independent sets in bounded-degree graphs
This page was built for publication: Greed is good: approximating independent sets in sparse and bounded-degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817635)
