Compact name-independent routing with minimum stretch

DOI10.1145/1367064.1367077zbMath1445.68143OpenAlexW1967359086MaRDI QIDQ4962742

Dahlia Malkhi, Cyril Gavoille, Ittai Abraham, Mikkel Thorup, Noam Nisan

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.6034

zbMATH Keywords

compact routing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (12)

Name-independent compact routing in trees ⋮ Strong-diameter decompositions of minor free graphs ⋮ Distance estimation and object location via rings of neighbors ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Compact roundtrip routing with topology-independent node names ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ Shortest-path queries in static networks ⋮ Electric routing and concurrent flow cutting ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Labeling schemes for tree representation ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch

This page was built for publication: Compact name-independent routing with minimum stretch