Greed is good: approximating independent sets in sparse and bounded-degree graphs

DOI10.1145/195058.195221MaRDI QIDQ2817635zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Greedy approximations of independent sets in low degree graphs
• Publication:4938679
• Improved approximations of independent sets in bounded-degree graphs
• Independent Sets in Bounded-Degree Hypergraphs

Cited in

(22)

• Improved approximations of independent sets in bounded-degree graphs
• The \textsc{max quasi-independent set} problem
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• Minimum entropy combinatorial optimization problems
• Brief announcement: Simple and local independent set approximation
• Independent sets in bounded-degree hypergraphs
• 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
• scientific article; zbMATH DE number 1405697 (Why is no real title available?)
• Ultimate greedy approximation of independent sets in subcubic graphs
• Independent sets in graphs with triangles
• Independent Sets in Bounded-Degree Hypergraphs
• 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
• Greed is good for deterministic scale-free networks
• On approximation properties of the Independent set problem for degree 3 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)