The disjoint shortest paths problem

DOI10.1016/S0166-218X(97)00121-2zbMath0902.68147MaRDI QIDQ1392552

Tali Eilam Tzoreff

Publication date: 18 October 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

disjoint shortest paths problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Faster 2-Disjoint-Shortest-Paths Algorithm ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ A PERCOLATION MODEL OF MOBILE AD-HOC NETWORKS ⋮ Redundancy system design for an aircraft door management system ⋮ Simple undirected two-commodity integral flow with a unitary demand ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths ⋮ Almost disjoint paths and separating by forbidden pairs ⋮ Reactive synthesis without regret ⋮ Dynamic routing and wavelength assignment for multi-lightpath demands ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ Unnamed Item ⋮ Inserting an edge into a geometric embedding ⋮ Inserting an edge into a geometric embedding ⋮ Two disjoint shortest paths problem with non-negative edge length ⋮ The undirected two disjoint shortest paths problem ⋮ Walking through waypoints ⋮ Complexity of a classical flow restoration problem ⋮ The directed 2-linkage problem with length constraints ⋮ Shortest Two Disjoint Paths in Polynomial Time ⋮ The Directed Disjoint Shortest Paths Problem ⋮ Two edge-disjoint paths with length constraints ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• The complexity of finding two disjoint paths with min-max objective function
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. VII: Disjoint paths on a surface
• On orientations and shortest paths
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• Integer plane multiflows with a mixed number of demands
• Graph minors. IX: Disjoint crossed paths
• On the complexity of the disjoint paths problem
• Disjoint Paths—A Survey
• On Odd Cuts and Plane Multicommodity Flows
• A Polynomial Solution to the Undirected Two Paths Problem
• Planar Formulae and Their Uses
• Finding disjoint paths with different path-costs: Complexity and algorithms
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Finding k Disjoint Paths in a Directed Planar Graph
• The complexity of finding maximum disjoint paths with length constraints