Deterministic improved 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)57-60
Journal / PublicationInformation Processing Letters
Volume129
Early online date25 Sep 2017
StatePublished - Jan 2018

Abstract

In this paper, we study the deterministicconstruction of round-trip spanners for weighted directed graphs. We propose adeterministic algorithm which constructs, for any n-vertex graph G(V , E), around-trip spanner H(V , E′ ⊆ E) of stretch 2+ and size O((k/) · n1+1/k log(nw)), where w is the maximum edge weight of G. Notably,this is the first deterministic construction of round-trip spanners and itsstretch-size trade-off even improves the previous state-of-the-art randomizedalgorithm by Roditty et al. More specifically, the size is asymptoticallyreduced by a factor of k while the stretch factor remains the same. The resultis the first clear improvement on round-trip spanners after about ten years andre-raises the open question that how best we can hope for the stretchsizetrade-off of round-trip spanners in digraphs.

Research Area(s)

  • Deterministic algorithms, Graph algorithms, Graph spanners, Round-trip spanners, Shortest distances

Citation Format(s)

Deterministic improved round-trip spanners. / Zhu, Chun Jiang; Lam, Kam-Yiu.

In: Information Processing Letters, Vol. 129, 01.2018, p. 57-60.

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