论文标题
不包括密集未成年人的图形的低端捷径
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
论文作者
论文摘要
我们证明，直径$ d $的任何$ n $ node Graph $ g $都可以使用拥塞$ o（ΔD\ log n）$和扩张$ O（ΔD）$的快捷方式，其中$δ$是任何$ g $的最大边缘密度。我们的证明是简单，基本和建设性的 - 具有$ \tildeθ（ΔD）$ - 圆形分布式结构算法。我们的结果紧张至$ \ tilde {o}（1）$因素，并概括，简化，统一和增强几个先前的结果。例如，对于不包括固定未成年人的图形，即具有常数$δ$的图形，只有$ \ tilde {o}（d^2）$绑定的$ \ tilde {o}（d^2）$是基于非常技术性的证据而闻名的，该证明依赖于Robertson-Seymour-Seymour图形结构。 我们结果的直接后果是，许多图形家族（包括任何次要隔离的家族）几乎具有最佳的$ \tildeθ（d）$ - 圆形分布式算法，用于许多基本的交流基原始人和优化问题，包括最小跨度树，最小切割和最短的路径近似。
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, elementary, and constructive - featuring a $\tildeΘ(δD)$-round distributed construction algorithm. Our results are tight up to $\tilde{O}(1)$ 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 $\tilde{O}(D^2)$ 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 that many graph families, including any minor-excluded ones, have near-optimal $\tildeΘ(D)$-round distributed algorithms for many fundamental communication primitives and optimization problems including minimum spanning tree, minimum cut, and shortest-path approximations.
