A simple local 3-approximation algorithm for vertex cover

DOI10.1016/J.IPL.2009.02.017MaRDI QIDQ987844zbMATH OpenOpenAlexFDO

Authors Valentin Polishchuk, Jukka Suomela

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

distributed computingapproximation algorithmsgraph algorithmslocal algorithms

Mathematics Subject Classification ID

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

Recommendations

• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• Approximated distributed minimum vertex cover algorithms for bounded degree graphs
• Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers

Cites work

• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Distributed Weighted Matching
• Efficient Distributed Weighted Matchings on Trees
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• Linear programming without the matrix
• Locality in Distributed Graph Algorithms
• On the distributed complexity of computing maximal matchings
• The price of being near-sighted
• What Can be Computed Locally?
• What cannot be computed locally!

Cited in

(13)

• Approximation in (poly-) logarithmic space
• Local computation: lower and upper bounds
• Weak models of distributed computing, with connections to modal logic
• A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks
• Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• Approximation in (Poly-) Logarithmic Space
• scientific article; zbMATH DE number 3853143 (Why is no real title available?)
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Local approximability of max-min and min-max linear programs
• Optimal distributed covering algorithms
• Minimum vertex cover in ball graphs through local search

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987844)