Quadratic and near-quadratic lower bounds for the CONGEST model

From MaRDI portal

Revision as of 14:37, 28 November 2024 by Import241128011130 (talk | contribs) (Created automatically from import241128011130)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:6487481

Jump to:navigation, search

DOI10.4230/LIPICS.DISC.2017.10zbMath1515.6823MaRDI QIDQ6487481

Keren Censor-Hillel, Ami Paz, Seri Khoury

Publication date: 3 February 2023

zbMATH Keywords

chromatic number lower bounds minimum vertex cover CONGEST weighted APSP

Mathematics Subject Classification ID

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

Related Items (8)

Distributed Testing of Distance-k Colorings ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ Detecting cliques in CONGEST networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Unnamed Item ⋮ Simple and local independent set approximation ⋮ Distributed Spanner Approximation ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

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

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:6487481&oldid=37945816"