Interval routing in reliability networks

DOI10.1016/j.tcs.2004.12.008zbMath1090.68001MaRDI QIDQ1770375

Martin Nehéz, Cyril Gavoille

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.12.008

zbMATH Keywords

Random graphs; Compact routing tables; Interval routing; Percolation theory; Reliability networks

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68M10: Network design and communication in computer systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
• The complexity of shortest path and dilation bounded interval routing
• A survey on interval routing
• The complexity of the characterization of networks supporting shortest-path interval routing.
• Compact Routing with Minimum Stretch
• The Compactness of Interval Routing for Almost All Graphs
• The small-world phenomenon
• Labelling and Implicit Routing in Networks
• Interval Routing
• Efficient Message Routing in Planar Networks
• The Complexity of Interval Routing on Random Graphs
• Worst Case Bounds for Shortest Path Interval Routing
• Percolation
• On the space requirement of interval routing
• Expander properties in random regular graphs with edge faults
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• The Compactness of Interval Routing
• A trade-off between space and efficiency for routing tables
• Compact routing schemes with low stretch factor
• Proximity-preserving labeling schemes
• Universal routing schemes
• (1 + εΒ) -spanner constructions for general graphs
• CONNECTIVITY PROPERTIES IN RANDOM REGULAR GRAPHS WITH EDGE FAULTS
• Compact oracles for reachability and approximate distances in planar digraphs
• Depth-First Search and Linear Graph Algorithms