Quadratic and near-quadratic lower bounds for the CONGEST model

DOI10.4230/LIPICS.DISC.2017.10zbMATH Open1515.6823MaRDI QIDQ6487481FDOQ6487481

Keren Censor-Hillel, Ami Paz, Seri Khoury

Publication date: 3 February 2023

Recommendations

• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Parameterized distributed algorithms
• Approximation of distances and shortest paths in the broadcast congest clique

zbMATH Keywords

lower boundschromatic numberminimum vertex coverCONGESTweighted APSP

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Cited In (11)

• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed Testing of Distance-k Colorings
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Title not available (Why is that?)
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• Improved distributed approximations for maximum independent set
• Simple and local independent set approximation
• Detecting cliques in CONGEST networks
• Distributed maximum matching verification in CONGEST
• Improved hardness of approximation of diameter in the CONGEST model
• Distributed Spanner Approximation

This page was built for publication: Quadratic and near-quadratic lower bounds for the CONGEST model

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