The complexity of the characterization of networks supporting shortest-path interval routing.

DOI10.1016/S0304-3975(01)00180-3zbMath1061.68009MaRDI QIDQ1853562

Shlomo Moran, Shmuel Zaks, Tamar Eilam

Publication date: 21 January 2003

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

zbMATH Keywords

Communication networksInterval routingCompact routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

All-shortest-path 2-interval routing is NP-complete, Interval routing in some planar networks., Interval Routing Schemes for Circular-Arc Graphs, Compact and localized distributed data structures, On the hardness of minimizing space for all-shortest-path interval routing schemes, Interval routing in reliability networks, The compactness of adaptive routing tables, A survey on interval routing, Ordered interval routing schemes, Static and dynamic low-congested interval routing schemes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Designing networks with compact routing tables
• On interval routing schemes and treewidth
• A survey on interval routing
• Labelling and Implicit Routing in Networks
• Interval Routing
• Worst Case Bounds for Shortest Path Interval Routing
• Partial characterizations of networks supporting shortest path interval labeling schemes
• Interval routing schemes
• A trade-off between space and efficiency for routing tables
• Compact routing schemes with low stretch factor
• On Multi-Label Linear Interval Routing Schemes
• A characterization of networks supporting linear interval routing