Metadata only
Date
2021-07Type
- Conference Paper
Abstract
We prove that any n-node graph G with diameter D admits shortcuts with congestion O(δD log n) and dilation O(δD), where δis the maximum edge-density of any minor of G. Our proof is simple and constructive with a tildeΘ (δD)-round1 distributed construction algorithm. Our results are tight up to logarithmic factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant δ, only a O (D2) bound was known based on a very technical proof that relies on the Robertson-Seymour Graph Structure Theorem. A direct consequence of our result is this: many graph families, including any minor-excluded ones, have near-optimal tildeΘ(D)-round distributed algorithms for many fundamental communication primitives and optimization problems in the standard synchronous message-passing model with logarithmic message sizes, i.e., the CONGEST model. These problems include minimum spanning tree, minimum cut approximation, and shortest-path approximations. Show more
Publication status
publishedExternal links
Book title
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)Pages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
Distributed graph algorithms; Low-congestion shortcuts; Minor excluded graphs; Planar graphs; Congestion; Dilation; Minimum spanning treeOrganisational unit
08730 - Gruppe Häupler / Group Häupler
Funding
853109 - Distributed and Massively Parallel Graph Algorithms (EC)
184735 - Distributed Algorithms for Global Graph Problems (SNF)
More
Show all metadata