Complexity of pairwise shortest path routing in the grid

DOI10.1016/J.TCS.2004.06.027zbMath1071.68004OpenAlexW2162858941MaRDI QIDQ703544

David Serena, Teofilo F. Gonzalez

Publication date: 11 January 2005

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

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

zbMATH Keywords

NP-completenessFault-toleranceEdge disjoint shortest pathsGrid networksNode disjoint shortest paths

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (1)

Pairwise edge disjoint shortest paths in the \(n\)-cube

Cites Work

• Unnamed Item
• Global wire routing in two-dimensional arrays
• Complexity and approximations for multimessage multicasting
• A linear time algorithm for unique Horn satisfiability
• Routing a permutation in the hypercube by two sets of edge disjoint paths
• From Hall's matching theorem to optimal routing on hypercubes
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Efficient dispersal of information for security, load balancing, and fault tolerance
• On the Computational Complexity of Combinatorial Problems
• Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout

This page was built for publication: Complexity of pairwise shortest path routing in the grid