A linear time algorithm for the induced disjoint paths problem in planar graphs
DOI10.1016/J.JCSS.2011.10.004zbMATH Open1241.05058OpenAlexW2020972784MaRDI QIDQ414938FDOQ414938
Authors: Ken-ichi Kawarabayashi, Yusuke Kobayashi 
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.10.004
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)
Cites Work
- Maximal Flow Through a Network
- Graph minors. XIII: The disjoint paths problem
- Graphs on surfaces
- The strong perfect graph theorem
- Recognizing Berge graphs
- The disjoint paths problem in quadratic time
- On the Computational Complexity of Combinatorial Problems
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Title not available (Why is that?)
- The complexity of induced minors and related problems
- Finding k Disjoint Paths in a Directed Planar Graph
- Induced disjoint paths problem in a planar digraph
- Graph minors. VII: Disjoint paths on a surface
- Rooted routing in the plane
- Graph minors. XI: Circuits on a surface
- Induced circuits in planar graphs
- Title not available (Why is that?)
- Non-interfering network flows
Cited In (22)
- Induced disjoint paths in AT-free graphs
- Few induced disjoint paths for \(H\)-free graphs
- Few induced disjoint paths for \(H\)-free graphs
- Finding a shortest even hole in polynomial time
- Title not available (Why is that?)
- Induced disjoint paths in circular-arc graphs in linear time
- The Induced Disjoint Paths Problem
- LINEAR-TIME ALGORITHMS FOR DISJOINT TWO-FACE PATHS PROBLEMS IN PLANAR GRAPHS
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- A near-linear-time algorithm for computing replacement paths in planar directed graphs
- Title not available (Why is that?)
- An exponential time parameterized algorithm for planar disjoint paths
- Induced disjoint paths in claw-free graphs
- Graph editing to a fixed target
- Combing a Linkage in an Annulus
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- Parameterizing path partitions
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Induced disjoint paths in circular-arc graphs in linear time
- Induced disjoint paths problem in a planar digraph
- Algorithms for finding an induced cycle in planar graphs
This page was built for publication: A linear time algorithm for the induced disjoint paths problem in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414938)
