Approximated distributed minimum vertex cover algorithms for bounded degree graphs

DOI10.1007/978-3-642-14031-0_13MaRDI QIDQ3578307zbMATH OpenOpenAlexFDO

Authors Yong Zhang, Francis Y. L. Chin, Hing-Fung Ting

Publication date 20 July 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14031-0_13

Mathematics Subject Classification ID

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

Recommendations

• 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
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Computing and Combinatorics

Cited in

(12)

• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• On the distributed decision-making complexity of the minimum vertex cover problem
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• Distributed weighted vertex cover via maximal matchings
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• What cannot be computed locally!
• Computing and Combinatorics
• Minimum vertex cover, distributed decision-making, and communication complexity
• Parameterized distributed algorithms
• A simple local 3-approximation algorithm for vertex cover

This page was built for publication: Approximated distributed minimum vertex cover algorithms for bounded degree graphs

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