Local routing in a tree metric 1-spanner

Milutin Brankovic (), Joachim Gudmundsson () and André van Renssen ()
Additional contact information
Milutin Brankovic: University of Sydney
Joachim Gudmundsson: University of Sydney
André van Renssen: University of Sydney

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 26, 2642-2660

Abstract: Abstract Solomon and Elkin (SIAM J Discret Math 28(3):1173–1198, 2014) constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $$(1+\epsilon )$$ ( 1 + ϵ ) -spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $$O(\log n)$$ O ( log n ) hops and requires $$O(\varDelta \log n)$$ O ( Δ log n ) bits of storage per vertex where $$\varDelta $$ Δ is the maximum degree of the tree on which the spanner is constructed. This local routing algorithm can be adapted to a local routing algorithm for a doubling metric spanner which makes use of the shortcutting scheme.

Keywords: Local routing; Spanners; Weighted trees; Doubling metrics (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00784-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00784-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00784-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().