All-shortest-path 2-interval routing is NP-complete

DOI10.1007/s12190-009-0265-2zbMath1215.05192OpenAlexW2090736241MaRDI QIDQ2380872

Yan Yan Liu, Rui Wang, Kai Wang

Publication date: 12 April 2010

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12190-009-0265-2

zbMATH Keywords

NP-completenesscompact routinginterval routing schemes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15)

Cites Work

• Unnamed Item
• Unnamed Item
• A survey on interval routing
• The compactness of adaptive routing tables
• 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
• The Planar Hamiltonian Circuit Problem is NP-Complete
• On Multi-Label Linear Interval Routing Schemes
• Structural Information and Communication Complexity
• A characterization of networks supporting linear interval routing
• Interval routing schemes

This page was built for publication: All-shortest-path 2-interval routing is NP-complete