It is hard to know when greedy is good for finding independent sets
DOI10.1016/S0020-0190(96)00208-6zbMATH Open1336.68094OpenAlexW2082456657MaRDI QIDQ286978FDOQ286978
Authors: Hans L. Bodlaender, Dimitrios M. Thilikos, Koichi Yamazaki 
Publication date: 26 May 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(96)00208-6
Recommendations
- Publication:4938679
- The greedier the better: an efficient algorithm for approximating maximum independent set
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Greed is good: approximating independent sets in sparse and bounded-degree graphs
- A note on the random greedy independent set algorithm
- GreedyMAX-type algorithms for the maximum independent set problem
- Problems on independence systems solvable by the greedy algorithm
- Greedy approximations of independent sets in low degree graphs
- A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Approximation algorithms for combinatorial problems
- Title not available (Why is that?)
- Well-covered claw-free graphs
- Greed is good: approximating independent sets in sparse and bounded-degree graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Recognizing Greedy Structures
Cited In (6)
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- Ultimate greedy approximation of independent sets in subcubic graphs
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
- Recognizing well-dominated graphs is coNP-complete
- Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
- Optimal monotone relabelling of partially non-monotone ordinal data
This page was built for publication: It is hard to know when greedy is good for finding independent sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286978)
