A Local 2-Approximation Algorithm for the Vertex Cover Problem
From MaRDI portal
Publication:3646226
DOI10.1007/978-3-642-04355-0_21zbMath1261.68161OpenAlexW1813487646MaRDI QIDQ3646226
Valentin Polishchuk, Jukka Suomela, Jara Uitto, Matti Åstrand, Joel Rybicki, Patrik Floréen
Publication date: 19 November 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10138/27930
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items (10)
Fast Distributed Approximation for Max-Cut ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Distributed half-integral matching and beyond ⋮ Distributed half-integral matching and beyond ⋮ Optimal distributed covering algorithms ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Local approximability of max-min and min-max linear programs ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Weak models of distributed computing, with connections to modal logic
This page was built for publication: A Local 2-Approximation Algorithm for the Vertex Cover Problem
