Complexity of pairwise shortest path routing in the grid

DOI10.1016/J.TCS.2004.06.027MaRDI QIDQ703544zbMATHOpenAlexFDO

Authors Teofilo F. Gonzalez, David Serena

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

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

Recommendations

• Pairwise edge disjoint shortest paths in the \(n\)-cube
• The disjoint shortest paths problem
• scientific article; zbMATH DE number 4211829
• Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
• Distributed algorithms for computing shortest pairs of disjoint paths

Cites work

• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• A linear time algorithm for unique Horn satisfiability
• Complexity and approximations for multimessage multicasting
• Efficient dispersal of information for security, load balancing, and fault tolerance
• From Hall's matching theorem to optimal routing on hypercubes
• Global wire routing in two-dimensional arrays
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout
• On the Computational Complexity of Combinatorial Problems
• Routing a permutation in the hypercube by two sets of edge disjoint paths

Cited in

(6)

• On finding non-intersecting straightline connections of grid points to the boundary
• Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
• scientific article; zbMATH DE number 1990700 (Why is no real title available?)
• The complexity of routing with few collisions
• Pairwise edge disjoint shortest paths in the \(n\)-cube
• On interdependent failure resilient multi-path routing in smart grid communication network

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703544)