A simple local 3-approximation algorithm for vertex cover

DOI10.1016/j.ipl.2009.02.017zbMath1214.68468OpenAlexW2101781054MaRDI QIDQ987844

Jukka Suomela, Valentin Polishchuk

Publication date: 16 August 2010

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

Full work available at URL: http://hdl.handle.net/10138/27927

zbMATH Keywords

graph algorithmsdistributed computingapproximation algorithmslocal algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (8)

Optimal distributed covering algorithms ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Local approximability of max-min and min-max linear programs ⋮ A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks ⋮ Approximation in (Poly-) logarithmic space ⋮ 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 ⋮ Approximation in (Poly-) Logarithmic Space

Cites Work

• Unnamed Item
• On the Distributed Complexity of Computing Maximal Matchings
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• The price of being near-sighted
• Efficient Distributed Weighted Matchings on Trees
• Locality in Distributed Graph Algorithms
• What Can be Computed Locally?
• Linear programming without the matrix
• Distributed Weighted Matching
• What cannot be computed locally!

This page was built for publication: A simple local 3-approximation algorithm for vertex cover