On the hardness of minimizing space for all-shortest-path interval routing schemes

DOI10.1016/j.tcs.2007.09.010zbMath1143.68012OpenAlexW2124856550MaRDI QIDQ2465642

Yanyan Li

Publication date: 7 January 2008

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

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

zbMATH Keywords

NP-completenesscompact routinginterval routing schemes

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• A survey on interval routing
• The complexity of the characterization of networks supporting shortest-path interval routing.
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Characterization results of all shortest paths interval routing schemes
• Labelling and Implicit Routing in Networks
• Interval Routing
• Structural Information and Communication Complexity
• A characterization of networks supporting linear interval routing
• Interval routing schemes

This page was built for publication: On the hardness of minimizing space for all-shortest-path interval routing schemes