In this paper, we study the problem of efficiently constructing source-wise round-trip spanners in weighted directed graphs. For a source vertex set S\subseteq V in a digraph G(V,E), an S-source-wise round-trip spanner of G of stretch k is a subgraph H of G such that for every u\in S ,v\in V, the round-trip distance between u and v in H is at most k times of the original distance in G. We show that , for a digraph G(V,E) with n vertices , m edgesand nonnegative edge weights , an s-sized source vertex set S\subseteq V and a positive integer k , there exists an algorithm , in time O(ms^{1/k}\log^5n) , with high probability constructing an S-source-wise round-trip spanner of stretch O(k\log n) and size O(ns^{1/k}\log^2n) . Compared with the state of the art}\hspace{0pt}%DIFAUXCMD , 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 }\hspace{0pt}%DIFAUXCMD } , our algorithm significantly improves their construction time \Omega(\min\{ms,n^\omega\}) (where \omega \in [2,2.373) and 2.373 is the matrix multiplication exponent) to nearly linear O(ms^{1/k}\log^5n), while still keeping a spanner stretch O(k \log n) and size O(ns^{1/k\log^2n), asymptotically similar to their stretch 2k+\epsilon and size O((k^2/\epsilon)ns^{1/k}\log(nw)), respectively}  }\hspace{0pt}%DIFAUXCMD can be adapted to the source-wise setting} .
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 \mbox{%DIFAUXCMD \cite{PRS+18,CLR+20}\hspace{0pt}%DIFAUXCMD , 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 \mbox{%DIFAUXCMD \cite{ZL17}\hspace{0pt}%DIFAUXCMD } , our algorithm significantly improves their construction time \Omega(\min\{ms,n^\omega\}) (where \omega \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) \log^2n), asymptotically similar to their stretch 2k+\epsilon and size O((k^2/\epsilon)ns^{1/k}\log(nw)), respectively} 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 \mbox{%DIFAUXCMD \cite{PRS+18 }\hspace{0pt}%DIFAUXCMD can be adapted to the source-wise setting} .
R
efficiently constructing
fast constructions of
R
digraph
graph
R
S-source-wise
S-sourcewise
R
u\in S
pair of vertices u
R
V, the
S\times V, their
D
between u and v
R
the original
their round-trip
R
, for a digraph
for a graph
R
, m edgesand nonnegative edge weights
and m edges
R
a positive integer k
an integer k>1
R
,
that
R
, with high probability constructing an S-source-wise
constructs an S-sourcewise
D
size
R
. Compared with the state of the art
edges with high probability. Compared to the fast algorithms for constructing all-pairs round-trip spanners \mbox{%DIFAUXCMD \cite{PRS+18,CLR+20
A
\mbox{%DIFAUXCMD \cite{ZL17
R
while still keeping a spanner stretch O(k
at the expense of paying an extra O(
D
and size O(ns^{1/k
A
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 \mbox{%DIFAUXCMD \cite{PRS+18