On shortest disjoint paths in planar graphs

DOI10.1016/J.DISOPT.2010.05.002MaRDI QIDQ429668zbMATH OpenOpenAlexFDO

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

disjoint pathsminimum cost flowobjective functionplanar graphshortest path

Mathematics Subject Classification ID

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

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

• 2-linked graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on two problems in connexion with graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• 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
• 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?)
• 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

(50)

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

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)