Parameterized distributed algorithms

DOI10.4230/LIPICS.DISC.2019.6MaRDI QIDQ6487523zbMATH OpenFDO

Authors Ran Ben-Basat, Ken-ichi Kawarabayashi, Gregory Schwartzman

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2019.6

zbMATH Keywords

approximation algorithmsdistributed algorithmsparameterized algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• What cannot be computed locally!
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• 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

Cited in

(5)

• Fast Distributed Algorithms for Computing Separable Functions
• Hardness of Distributed Optimization
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Distributed maximum matching verification in CONGEST
• Parameterized quantum query algorithms for graph problems

This page was built for publication: Parameterized distributed algorithms

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