A survey on interval routing

DOI10.1016/S0304-3975(99)00283-2zbMath0946.68002MaRDI QIDQ1575744

Cyril Gavoille

Publication date: 21 August 2000

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

zbMATH Keywords

networkscompact routingbroadcastinginterval routingrouting tables

Mathematics Subject Classification ID

Distributed systems (68M14)

Related Items (23)

New bounds for multi-label interval routing ⋮ How to use spanning trees to navigate in graphs ⋮ A SURVEY ON UNDIRECTED CIRCULANT GRAPHS ⋮ All-shortest-path 2-interval routing is NP-complete ⋮ Average stretch analysis of compact routing schemes ⋮ Interval routing in some planar networks. ⋮ Distributed computing of efficient routing schemes in generalized chordal graphs ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ Interval routing schemes allow broadcasting with linear message-complexity ⋮ Compact and localized distributed data structures ⋮ On the hardness of minimizing space for all-shortest-path interval routing schemes ⋮ Characterization results of all shortest paths interval routing schemes ⋮ Characterization of networks supporting multi-dimensional linear interval routing schemes ⋮ Interval routing in reliability networks ⋮ Low-congested interval routing schemes for hypercubelike networks ⋮ On compact and efficient routing in certain graph classes ⋮ The compactness of adaptive routing tables ⋮ Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs ⋮ A short note on the lower bound of dilation for \(O(\log n)\)-label interval routing ⋮ Ordered interval routing schemes ⋮ Threshold dominating cliques in random graphs and interval routing ⋮ Unnamed Item ⋮ The complexity of the characterization of networks supporting shortest-path interval routing.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the impact of sense of direction on message complexity
• Designing networks with compact routing tables
• Multidimensional interval routing schemes
• Treewidth. Computations and approximations
• On interval routing schemes and treewidth
• On the complexity of multi-dimensional interval routing schemes
• Static and dynamic low-congested interval routing schemes
• On forwarding indices of networks
• The complexity of the characterization of networks supporting shortest-path interval routing.
• Sense of direction in distributed computing
• Topology of series-parallel networks
• Characterization results of all shortest paths interval routing schemes
• The Compactness of Interval Routing for Almost All Graphs
• Memory requirement for routing in distributed networks
• Optimal routing tables
• Labelling and Implicit Routing in Networks
• Space-Efficient Message Routing inc-Decomposable Networks
• The complexity of interval routing on random graphs
• Interval Routing
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Worst Case Bounds for Shortest Path Interval Routing
• Partial characterizations of networks supporting shortest path interval labeling schemes
• Sense of direction: Definitions, properties, and classes
• Lower bounds for compact routing
• Interval routing schemes
• A trade-off between space and efficiency for routing tables
• Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
• Compact routing schemes with low stretch factor
• Deadlock-free interval routing schemes
• Universal routing schemes
• Interval routing schemes

This page was built for publication: A survey on interval routing