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

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

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

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

combinatorial problems; analysis of algorithms; approximation algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP