It is hard to know when greedy is good for finding independent sets

DOI10.1016/S0020-0190(96)00208-6MaRDI QIDQ286978zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

analysis of algorithmsapproximation algorithmscombinatorial problems

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1003268 (Why is no real title available?)
• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• scientific article; zbMATH DE number 578252 (Why is no real title available?)
• Approximation algorithms for combinatorial problems
• Greed is good: approximating independent sets in sparse and bounded-degree graphs
• Recognizing Greedy Structures
• Well-covered claw-free graphs

Cited in

(6)

• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• Ultimate greedy approximation of independent sets in subcubic graphs
• 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)