The Compactness of Interval Routing for Almost All Graphs

DOI10.1137/S0097539799351717zbMath0990.05118OpenAlexW2092319564MaRDI QIDQ2784477

Cyril Gavoille, David Peleg

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539799351717

zbMATH Keywords

random graphscompact routinginterval routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Average stretch analysis of compact routing schemes ⋮ Distributed computing of efficient routing schemes in generalized chordal graphs ⋮ Compact and localized distributed data structures ⋮ Interval routing in reliability networks ⋮ Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs ⋮ A survey on interval routing ⋮ Threshold dominating cliques in random graphs and interval routing

This page was built for publication: The Compactness of Interval Routing for Almost All Graphs