Complexity of pairwise shortest path routing in the grid

DOI10.1016/J.TCS.2004.06.027zbMATH Open1071.68004OpenAlexW2162858941MaRDI QIDQ703544FDOQ703544

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

Recommendations

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Pairwise edge disjoint shortest paths in the \(n\)-cube
• The complexity of routing with few collisions
• 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)