scientific article; zbMATH DE number 1953099

MaRDI QIDQ4414503zbMATH OpenFDO

Authors Edith Hemaspaandra, Jörg Rothe, Holger Spakowski

Publication date 25 July 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2573/25730258.htm

zbMATH Keywords

approximationcompletenessComputational complexityminimum vertex cover heuristicsparallel access to NP

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 8779
• A graph approximation heuristic for the vertex cover problem on planar graphs
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• A list heuristic for vertex cover

Cited in

(3)

• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
• scientific article; zbMATH DE number 8779 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4414503)