The compactness of interval routing for almost all graphs

DOI10.1137/S0097539799351717MaRDI QIDQ2784477zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The Compactness of Interval Routing
• The complexity of shortest path and dilation bounded interval routing
• The Complexity of Interval Routing on Random Graphs
• The complexity of interval routing on random graphs
• Interval routing schemes

Cited in

(17)

• The Compactness of Interval Routing
• Algorithms and Computation
• Compact and localized distributed data structures
• The Complexity of Interval Routing on Random Graphs
• Interval routing schemes for circular-arc graphs
• Distributed computing of efficient routing schemes in generalized chordal graphs
• Average stretch analysis of compact routing schemes
• Distributed computing of efficient routing schemes in generalized chordal graphs
• Searching among intervals and compact routing tables
• All-shortest-path 2-interval routing is NP-complete
• On the hardness of minimizing space for all-shortest-path interval routing schemes
• A survey on interval routing
• Counterexamples to the uniform shortest path routing conjecture for vertex-transitive graphs
• Searching among intervals and compact routing tables
• Threshold dominating cliques in random graphs and interval routing
• The complexity of interval routing on random graphs
• Interval routing in reliability networks

This page was built for publication: The compactness of interval routing for almost all graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784477)