On shortest disjoint paths in planar graphs

DOI10.1016/J.DISOPT.2010.05.002MaRDI QIDQ429668zbMATHOpenAlexFDO

Authors Yusuke Kobayashi, C. 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

objective functionshortest pathplanar graphdisjoint pathsminimum cost flow

Mathematics Subject Classification ID

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

Recommendations

• On shortest disjoint paths in planar graphs
• Towards single face shortest vertex-disjoint paths in undirected planar graphs
• The disjoint shortest paths problem
• scientific article; zbMATH DE number 6146454
• On finding Min-Min disjoint paths

Cites work

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

Cited in

(44)

• Selecting vertex disjoint paths in plane graphs
• Planar disjoint-paths completion
• The directed 2-linkage problem with length constraints
• On shortest disjoint paths in planar graphs
• scientific article; zbMATH DE number 7561373 (Why is no real title available?)
• Paths of low weight in planar graphs
• The Vertex-Disjoint Menger Problem in Planar Graphs
• Irrelevant vertices for the planar disjoint paths problem
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• On finding Min-Min disjoint paths
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• scientific article; zbMATH DE number 7561324 (Why is no real title available?)
• Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
• Shortest paths in intersection graphs of unit disks
• The Directed Disjoint Shortest Paths Problem
• The multiple Steiner TSP with order constraints: complexity and optimization algorithms
• On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
• Short disjoint paths in locally connected graphs
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• On the computational complexity of closest genome problems
• Shortest two disjoint paths in polynomial time
• On the edge capacitated Steiner tree problem
• scientific article; zbMATH DE number 4110723 (Why is no real title available?)
• Improved approximation for node-disjoint paths in planar graphs
• Induced disjoint paths problem in a planar digraph
• scientific article; zbMATH DE number 6146454 (Why is no real title available?)
• scientific article; zbMATH DE number 6850313 (Why is no real title available?)
• Shortest \((A+B)\)-path packing via hafnian
• Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs
• Disjoint Paths in a Planar Graph—A General Theorem
• Shortest edge-disjoint paths in graphs
• Finding paths with minimum shared edges
• The non-stop disjoint trajectories problem
• On the connectivity preserving minimum cut problem
• Planar disjoint-paths completion
• An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization
• Length-bounded disjoint paths in planar graphs
• Inserting Multiple Edges into a Planar Graph
• Towards single face shortest vertex-disjoint paths in undirected planar graphs
• Inserting an edge into a geometric embedding
• The undirected two disjoint shortest paths problem
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• On the approximability of time disjoint walks
• Inserting an edge into a geometric embedding

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

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