Interval Routing

DOI10.1093/comjnl/30.4.298zbMath0652.68051OpenAlexW2914484629MaRDI QIDQ3798237

Richard B. Tan, Jan van Leeuwen

Publication date: 1987

Published in: The Computer Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/comjnl/30.4.298

zbMATH Keywords

message complexityinterval routingdistributive networkgeneration of spanning treesleader- finding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)

Related Items

New bounds for multi-label interval routing ⋮ An optimal message routing algorithm for double-loop networks ⋮ Deadlock-free interval routing schemes ⋮ All-shortest-path 2-interval routing is NP-complete ⋮ Designing networks with compact routing tables ⋮ On devising Boolean Routing Schemes ⋮ Multi-dimensional Interval Routing Schemes ⋮ On devising Boolean Routing schemes ⋮ Interval routing in some planar networks. ⋮ On multi-label linear interval routing schemes ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ Universal routing schemes ⋮ 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 ⋮ Graphs with bounded induced distance ⋮ Representing graphs implicitly using almost optimal space ⋮ Max-stretch reduction for tree spanners ⋮ Characterization of networks supporting multi-dimensional linear interval routing schemes ⋮ Interval routing in reliability networks ⋮ Interval routing schemes ⋮ Low-congested interval routing schemes for hypercubelike networks ⋮ A fault-tolerant routing scheme in dynamic networks ⋮ On compact and efficient routing in certain graph classes ⋮ A note on models for graph representations ⋮ Multidimensional interval routing schemes ⋮ The compactness of adaptive routing tables ⋮ The complexity of shortest path and dilation bounded interval routing ⋮ A survey on interval routing ⋮ On the complexity of multi-dimensional interval routing schemes ⋮ A short note on the lower bound of dilation for \(O(\log n)\)-label interval routing ⋮ Ordered interval routing schemes ⋮ The complexity of the characterization of networks supporting shortest-path interval routing. ⋮ Static and dynamic low-congested interval routing schemes ⋮ Graph theoretical issues in computer networks