On shortest disjoint paths in planar graphs

DOI10.1016/j.disopt.2010.05.002zbMath1241.90163MaRDI 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 path; minimum cost flow; objective function; planar graph; disjoint paths

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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