Distributed algorithms for computing shortest pairs of disjoint paths

DOI10.1109/18.212275MaRDI QIDQ4202064zbMATH OpenOpenAlexFDO

Authors Richard G. Ogier, Vlad Rutenburg, Nachum Shacham

Publication date 13 January 1994

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/18.212275

zbMATH Keywords

shortest pathdisjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• A quick method for finding shortest pairs of disjoint paths
• Theory and Applications of Models of Computation
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• A distributed shortest path algorithm for a planar network
• An ‘All Pairs Shortest Paths’ Distributed Algorithm Using 2n2Messages

Cited in

(33)

• Sharing information for the all pairs shortest path problem
• New solutions for disjoint paths in P systems
• Efficient distributed algorithms for single-source shortest paths and related problems on plane networks
• A \(2\cdot | E |\)-bit distributed algorithm for the directed Euler trail problem
• The Directed Disjoint Shortest Paths Problem
• scientific article; zbMATH DE number 1304097 (Why is no real title available?)
• A quick method for finding shortest pairs of disjoint paths
• Lower bounds for approximate (\& exact) k-disjoint-shortest-paths
• Complexity of pairwise shortest path routing in the grid
• scientific article; zbMATH DE number 1512693 (Why is no real title available?)
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Theory and Applications of Models of Computation
• Pairwise edge disjoint shortest paths in the \(n\)-cube
• Acyclic k-connected subgraphs for distributed alternate routing in communications networks
• Safe and stabilizing distributed multi-path cellular flows
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Disjoint multipath routing using colored trees
• Shortest node-disjoint paths on random graphs
• Lower bounds for approximate (\& exact) \(k\)-\textsc{Disjoint-Shortest-Paths}
• Linear time distributed construction of colored trees for disjoint multipath routing
• ON ACHIEVING THE SHORTEST-PATH ROUTING IN 2-D MESHES
• A Stabilizing Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Networks
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• On shortest disjoint paths in planar graphs
• An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs
• Towards single face shortest vertex-disjoint paths in undirected planar graphs
• Path Problems in Complex Networks
• Toward fast calculation of communication paths for resilient routing
• Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
• Improved distributed algorithms for exact shortest paths
• Walking through waypoints
• A minimum-hop routing algorithm based on distributed information

This page was built for publication: Distributed algorithms for computing shortest pairs of disjoint paths

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