Source-wise round-trip spanners

In this paper, we study a new type of graph spanners, called source-wise round-trip spanners. Given any source vertex set SV in a directed graph G(V,E), such a spanner (with stretch k) has the property that the round-trip shortest path distance from any vertex sS to any vertex vV is at most k times of their round-trip distance in G. We present an algorithm to construct the source-wise round-trip spanners with stretch (2k+) and size O((k2/)ns1/klog(nw)) where n=|V|,s=|S| and w is the maximum edge weight. The result out-performs the state-of-the-art traditional round-trip spanners when the source vertex set S has small cardinality, and at the same time, it matches the traditional spanners when S is the whole vertex set V. We study a new type of graph spanners, called source-wise round-trip spanners.We present an algorithm for the source-wise round-trip spanners and its proof.The result outperforms the traditional spanner when the source vertex set is small.