Low-Congestion Shortcuts for Graphs Excluding Dense Minors
| Autor: | Bernhard Haeupler, Mohsen Ghaffari |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Optimization problem Logarithm Computer science Minor (linear algebra) 0102 computer and information sciences 02 engineering and technology Minimum spanning tree 01 natural sciences symbols.namesake Minimum cut Computer Science - Data Structures and Algorithms FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Discrete mathematics 020206 networking & telecommunications Graph structure theorem Planar graph Computer Science - Distributed Parallel and Cluster Computing 010201 computation theory & mathematics Distributed algorithm symbols Distributed Parallel and Cluster Computing (cs.DC) Combinatorics (math.CO) Distributed graph algorithms Low-congestion shortcuts Minor excluded graphs Planar graphs Congestion Dilation MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | PODC PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21) Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing |
| DOI: | 10.1145/3465084.3467935 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|