A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds

DOI10.1007/978-3-030-01325-7_21OpenAlexW2963800445MaRDI QIDQ1713914

Ran Ben-Basat, Gregory Schwartzman, Ken-ichi Kawarabayashi, Guy Even

Publication date: 30 January 2019

Full work available at URL: https://arxiv.org/abs/1804.01308

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx)

Related Items (4)

Optimal distributed covering algorithms ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Unnamed Item ⋮ Distributed set cover approximation: Primal-dual with optimal locality

This page was built for publication: A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds