Compact Routing with Minimum Stretch

DOI10.1006/jagm.2000.1134zbMath0969.68180OpenAlexW2077824753MaRDI QIDQ2709798

Lenore J. Cowen

Publication date: 17 April 2001

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2000.1134

zbMATH Keywords

routing algorithm

Mathematics Subject Classification ID

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

Related Items

Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ Models and algorithms for network reduction ⋮ Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Near-optimal induced universal graphs for cycles and paths ⋮ Compact routing messages in self-healing trees ⋮ New pairwise spanners ⋮ Unnamed Item ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ On the efficiency of routing in sensor networks ⋮ Compact and localized distributed data structures ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Fault-Tolerant Compact Routing Schemes for General Graphs ⋮ Compact Routing in Unit Disk Graphs ⋮ Compact roundtrip routing with topology-independent node names ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ An approximation algorithm for the edge-dilation \(k\)-center problem. ⋮ Unnamed Item ⋮ Interval routing in reliability networks ⋮ Transitive-Closure Spanners: A Survey ⋮ Close to linear space routing schemes ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Routing in Polygonal Domains