论文标题
用于源往返跨度跨越源的快速算法
A Fast Algorithm for Source-wise Round-trip Spanners
论文作者
论文摘要
在本文中，我们研究了加权定向图中源往返跨度跨越快速结构的问题。对于源顶点套件，图$ g（v，e）$，$ s $ s $ s $ s-sourcewise圆形旋转器的$ g $ a stretch $ k $是$ g $的$ g $ g $的$ g $ g $ g $的$ g $ g $，以至于每对$ u，v \ in $ h $ h $ h $ h $ h $ h $ k $ h $ h $ k $ h $ h $ h $ k $ h $ k $ h $ k $ h $ k $ h $ h $ h $ h $ h $ h $ h $ h $ h $我们表明，对于图形$ g（v，e）$，带有$ n $顶点和$ m $ edges，$ s $ s $ sized source source tertex set $ s \ subseteq v $和一个整数$ k> 1 $，存在一个algorithm，有一个时间$ o（ms^{1/k} \ log^5n）$ sletten $ sthent- $ O（k \ log n）$和$ O（NS^{1/k} \ log^2n）$ EDGE具有高概率。与用于构建全对往返跨行驶跨度的快速算法\ cite \ cite {prs+18，clr+20}相比，当$ k $是超级恒定时，我们的算法可以改善扳手的运行时间和边缘的数量。与现有的算法相比，用于构建源往返往返跨度\ cite {zl17}的算法相比，我们的算法显着改善了他们的构造时间$ω（\ min \ {ms，n^ω\}）$（其中$ω\ yn [2,2.373）$和2.373是$ 2.373 in IS linix incortions $ cultrix incortions for incortions in linirix difforents for in linirix usporention for in $ O（ms^{1/k} \ log^5n）$，牺牲在拉伸中支付额外的$ o（\ log n）$。作为算法的重要组成部分，我们开发了一个图形分区算法，将$ g $划分为有界半径的簇，并证明，在小往返距离时，每一个$ u，v \ in S \ times v $ in s s \ times v $，在不同簇中分离它们的可能性很小。该算法将$ S $的大小作为输入，并且不需要$ S $的知识。使用算法和可及性顶点估计算法，我们表明用于构建标准往返跨度跨度的递归算法\ cite \ cite {prs+18}可以适应源环境。
In this paper, we study the problem of fast constructions of source-wise round-trip spanners in weighted directed graphs. For a source vertex set $S\subseteq V$ in a graph $G(V,E)$, an $S$-sourcewise round-trip spanner of $G$ of stretch $k$ is a subgraph $H$ of $G$ such that for every pair of vertices $u,v\in S\times V$, their round-trip distance in $H$ is at most $k$ times of their round-trip distance in $G$. We show that for a graph $G(V,E)$ with $n$ vertices and $m$ edges, an $s$-sized source vertex set $S\subseteq V$ and an integer $k>1$, there exists an algorithm that in time $O(ms^{1/k}\log^5n)$ constructs an $S$-sourcewise round-trip spanner of stretch $O(k\log n)$ and $O(ns^{1/k}\log^2n)$ edges with high probability. Compared to the fast algorithms for constructing all-pairs round-trip spanners \cite{PRS+18,CLR+20}, our algorithm improve the running time and the number of edges in the spanner when $k$ is super-constant. Compared with the existing algorithm for constructing source-wise round-trip spanners \cite{ZL17}, our algorithm significantly improves their construction time $Ω(\min\{ms,n^ω\})$ (where $ω\in [2,2.373)$ and 2.373 is the matrix multiplication exponent) to nearly linear $O(ms^{1/k}\log^5n)$, at the expense of paying an extra $O(\log n)$ in the stretch. As an important building block of the algorithm, we develop a graph partitioning algorithm to partition $G$ into clusters of bounded radius and prove that for every $u,v\in S\times V$ at small round-trip distance, the probability of separating them in different clusters is small. The algorithm takes the size of $S$ as input and does not need the knowledge of $S$. With the algorithm and a reachability vertex size estimation algorithm, we show that the recursive algorithm for constructing standard round-trip spanners \cite{PRS+18} can be adapted to the source-wise setting.
