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

DOI10.1016/S0020-0190(96)00208-6zbMath1336.68094OpenAlexW2082456657MaRDI QIDQ286978

Koichi Yamazaki, Dimitrios M. Thilikos, Hans L. Bodlaender

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

combinatorial problemsanalysis of algorithmsapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (4)

Optimal monotone relabelling of partially non-monotone ordinal data ⋮ Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP ⋮ Recognizing well-dominated graphs is coNP-complete ⋮ Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

Cites Work

• Approximation algorithms for combinatorial problems
• Well-covered claw-free graphs
• Greed is good
• Recognizing Greedy Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: It is hard to know when greedy is good for finding independent sets