On shortest disjoint paths in planar graphs
From MaRDI portal
Publication:429668
DOI10.1016/J.DISOPT.2010.05.002zbMATH Open1241.90163OpenAlexW2004779317MaRDI QIDQ429668FDOQ429668
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
Recommendations
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Cites Work
- A note on two problems in connexion with graphs
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The directed subgraph homeomorphism problem
- Graph minors. XIII: The disjoint paths problem
- A Polynomial Solution to the Undirected Two Paths Problem
- The complexity of finding two disjoint paths with min-max objective function
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Disjoint paths in graphs
- 2-linked graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed algorithms for computing shortest pairs of disjoint paths
- The complexity of finding maximum disjoint paths with length constraints
- On the Computational Complexity of Combinatorial Problems
- S-functions for graphs
- Faster shortest-path algorithms for planar graphs
- Finding k Disjoint Paths in a Directed Planar Graph
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Title not available (Why is that?)
- Algorithms and Computation
Cited In (44)
- The Directed Disjoint Shortest Paths Problem
- The non-stop disjoint trajectories problem
- On shortest disjoint paths in planar graphs
- Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs
- Title not available (Why is that?)
- The undirected two disjoint shortest paths problem
- Shortest paths in intersection graphs of unit disks
- Improved approximation for node-disjoint paths in planar graphs
- Title not available (Why is that?)
- On the connectivity preserving minimum cut problem
- Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
- Short disjoint paths in locally connected graphs
- Title not available (Why is that?)
- Shortest \((A+B)\)-path packing via hafnian
- On the edge capacitated Steiner tree problem
- An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization
- The Vertex-Disjoint Menger Problem in Planar Graphs
- Title not available (Why is that?)
- Disjoint Paths in a Planar Graph—A General Theorem
- Length-bounded disjoint paths in planar graphs
- The multiple Steiner TSP with order constraints: complexity and optimization algorithms
- Planar disjoint-paths completion
- Selecting vertex disjoint paths in plane graphs
- Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
- Inserting an edge into a geometric embedding
- On the approximability of time disjoint walks
- On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
- Inserting Multiple Edges into a Planar Graph
- Planar disjoint-paths completion
- Irrelevant vertices for the planar disjoint paths problem
- Title not available (Why is that?)
- Finding paths with minimum shared edges
- Shortest two disjoint paths in polynomial time
- Shortest edge-disjoint paths in graphs
- Towards single face shortest vertex-disjoint paths in undirected planar graphs
- Complexity and approximation results for the min-sum and min-max disjoint paths problems
- On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- On the computational complexity of closest genome problems
- Induced disjoint paths problem in a planar digraph
- The directed 2-linkage problem with length constraints
- Inserting an edge into a geometric embedding
- Paths of low weight in planar graphs
- On finding Min-Min disjoint paths
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)
