A simple local 3-approximation algorithm for vertex cover
From MaRDI portal
Publication:987844
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
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