On shortest disjoint paths in planar graphs

DOI10.1016/J.DISOPT.2010.05.002zbMath1241.90163OpenAlexW2004779317MaRDI QIDQ429668

Yusuke Kobayashi, Christian Sommer

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.05.002

zbMATH Keywords

shortest pathminimum cost flowobjective functionplanar graphdisjoint paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs ⋮ On the connectivity preserving minimum cut problem ⋮ The multiple Steiner TSP with order constraints: complexity and optimization algorithms ⋮ Finding paths with minimum shared edges ⋮ Inserting Multiple Edges into a Planar Graph ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization ⋮ On the edge capacitated Steiner tree problem ⋮ Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Inserting an edge into a geometric embedding ⋮ Shortest \((A+B)\)-path packing via hafnian ⋮ Inserting an edge into a geometric embedding ⋮ On the approximability of time disjoint walks ⋮ On the computational complexity of closest genome problems ⋮ The directed 2-linkage problem with length constraints ⋮ Shortest Two Disjoint Paths in Polynomial Time ⋮ The Directed Disjoint Shortest Paths Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• The complexity of finding two disjoint paths with min-max objective function
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• S-functions for graphs
• Graph minors. XIII: The disjoint paths problem
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Graph minors. II. Algorithmic aspects of tree-width
• A Polynomial Solution to the Undirected Two Paths Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the Computational Complexity of Combinatorial Problems
• Distributed algorithms for computing shortest pairs of disjoint paths
• Finding k Disjoint Paths in a Directed Planar Graph
• The complexity of finding maximum disjoint paths with length constraints
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms and Computation
• Faster shortest-path algorithms for planar graphs

This page was built for publication: On shortest disjoint paths in planar graphs