Vertex Cover Gets Faster and Harder on Low Degree Graphs

DOI10.1007/978-3-319-08783-2_16zbMath1423.68199arXiv1404.5566OpenAlexW16538678MaRDI QIDQ2920457

Sathish Govindarajan, Akanksha Agrawal, Neeldhara Misra

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.5566

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) 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 algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Above guarantee parameterization for vertex cover on graphs with maximum degree 4

This page was built for publication: Vertex Cover Gets Faster and Harder on Low Degree Graphs