A quick method for finding shortest pairs of disjoint paths
From MaRDI portal
Publication:3330991
DOI10.1002/net.3230140209zbMath0542.90100OpenAlexW2155061423MaRDI QIDQ3330991
J. W. Suurballe, Robert Endre Tarjan
Publication date: 1984
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230140209
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05)
Related Items (44)
A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks ⋮ Multicriteria movement synchronization scheduling problems and algorithms ⋮ On finding Min-Min disjoint paths ⋮ Polynomial time algorithms for tracking path problems ⋮ Length-constrained cycle partition with an application to UAV routing* ⋮ A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem ⋮ Path Problems in Complex Networks ⋮ Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths ⋮ Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms ⋮ Finding disjoint paths with related path costs ⋮ Acyclic k-connected subgraphs for distributed alternate routing in communications networks ⋮ Algorithms for multicommodity flows in planar graphs ⋮ Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks ⋮ Two algorithms for minimum 2-connected \(r\)-hop dominating set ⋮ Finding paths with minimum shared edges ⋮ Single-commodity network design with random edge capacities ⋮ Linear time algorithms for two disjoint paths problems on directed acyclic graphs ⋮ A double oracle approach to minmax regret optimization problems with interval data ⋮ Finding \(K\) dissimilar paths: single-commodity and discretized flow formulations ⋮ Resilience of communication networks to random failures and disasters: An optimization perspective ⋮ Shared Risk Link Group disjointness and geodiverse routing: A trade‐off between benefit and practical effort ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ A Stabilizing Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Networks ⋮ A shortest cycle for each vertex of a graph ⋮ On the complexity of the edge-disjoint min-min problem in planar digraphs ⋮ Identifying Backbones in Three-Dimensional Discrete Fracture Networks: A Bipartite Graph-Based Approach ⋮ Fast approximation of matroid packing and covering ⋮ Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs ⋮ Fractional routing using pairs of failure-disjoint paths ⋮ An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs ⋮ An effective algorithm for obtaining the whole set of minimal cost pairs of disjoint paths with dual arc costs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ The complexity of finding two disjoint paths with min-max objective function ⋮ Algorithms for connected set cover problem and fault-tolerant connected set cover problem ⋮ Finding non-dominated bicriteria shortest pairs of disjoint simple paths ⋮ Solving the selective multi-category parallel-servicing problem ⋮ Unnamed Item ⋮ Finding disjoint paths in networks with star shared risk link groups ⋮ On Analysis of Traffic Flow Demultiplexing Effectiveness ⋮ Directed Steiner problems with connectivity constraints ⋮ Min-cost-flow preserving bijection between subgraphs and orientations ⋮ Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints
Cites Work
This page was built for publication: A quick method for finding shortest pairs of disjoint paths
