A simple local 3-approximation algorithm for vertex cover

DOI10.1016/J.IPL.2009.02.017zbMATH Open1214.68468OpenAlexW2101781054MaRDI QIDQ987844FDOQ987844

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

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

zbMATH Keywords

distributed computingapproximation algorithmsgraph algorithmslocal algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• 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
• Title not available (Why is that?)
• 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
• Approximation in (poly-) logarithmic space

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)