Low-congestion shortcut and graph parameters
Low-congestion shortcut and graph parameters
复制标题
低拥塞快捷方式和图形参数
DOI：
10.1007/s00446-021-00401-x
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Izumi Taisuke
中科院分区：
文献类型：
--
作者：
Kitamura Naoki;Kitagawa Hirotaka;Otachi Yota;Izumi Taisuke
标准CONGEST模型下的分布式图算法对于多个全局问题的时间复杂度下界为轮数，其中表示节点数，D表示输入图的直径。因为这样的下限是从特殊的“硬核”实例中导出的，所以它不一定适用于特定的流行图类，如平面图。低拥塞捷径的概念由Ghaffari和Haeupler [SODA 2016]提出，用于解决在受限网络拓扑中快速运行的CONGEST算法的设计。特别地，给定一个图类，构造质量为q的捷径的一个轮算法，在任何情况下，导致求解几个基本图问题，如最小生成树和最小割的轮算法，为。这条线上的主要兴趣是识别允许快捷方式的图形类，这些快捷方式在突破一般下界的意义上是有效的。在这项研究中，我们考虑低拥塞捷径的质量和以下四个主要的图形参数之间的关系：加倍维数，弦，直径，和candle-width。上界侧的关键成分是一种新的快捷构造技术，称为short-hop extension，这可能是独立的兴趣。
Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound ofrounds for several global problems, wherendenotes the number of nodes andDthe diameter of the input graph. Because such a lower bound is derived from special “hard-core” instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept oflow-congestion shortcutswas initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. In particular, given a graph class, anf-round algorithm for constructing shortcuts of qualityqfor any instance inresults in-round algorithms for solving several fundamental graph problems such as minimum spanning tree and minimum cut, for. The main interest on this line is to identify the graph classes allowing the shortcuts that are efficient in the sense of breaking-round general lower bounds. In this study, we consider the relationship between the quality of low-congestion shortcuts and the following four major graph parameters: doubling dimension, chordality, diameter, and clique-width. The key ingredient of the upper-bound side is a novel shortcut construction technique known asshort-hop extension, which might be of independent interest.