Source-wise round-trip spanners

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)42-45
Journal / PublicationInformation Processing Letters
Volume124
StatePublished - 1 Aug 2017

Abstract

In this paper, we study a new type of graph spanners, called source-wise round-trip spanners. Given any source vertex set S⊆V 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 s∈S to any vertex v∈V 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.

Research Area(s)

  • Graph algorithms, Graph spanners, Round-trip spanners, Shortest distance

Citation Format(s)

Source-wise round-trip spanners. / Zhu, Chun Jiang; Lam, Kam-Yiu.

In: Information Processing Letters, Vol. 124, 01.08.2017, p. 42-45.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal