On shortest disjoint paths in planar graphs
From MaRDI portal
Publication:429668
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
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, 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, 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