Deterministic improved round-trip spanners

Research output: Research - peer-review21_Publication in refereed journal

View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)57-60
Journal / PublicationInformation Processing Letters
Early online date25 Sep 2017
StatePublished - Jan 2018


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)