No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover

DOI10.1007/978-3-642-33651-5_13zbMath1377.68318arXiv1205.4605OpenAlexW1925030049MaRDI QIDQ4909410

Jukka Suomela, Mika Göös

Publication date: 13 March 2013

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

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

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 algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (2)

Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover

This page was built for publication: No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover