A linear time algorithm for the induced disjoint paths problem in planar graphs

DOI10.1016/J.JCSS.2011.10.004MaRDI QIDQ414938zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

induced subgraphplanar graphdisjoint pathslinear time algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Recommendations

• The Induced Disjoint Paths Problem
• Induced disjoint paths problem in a planar digraph
• Induced disjoint paths in circular-arc graphs in linear time
• Induced disjoint paths in circular-arc graphs in linear time
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

Cites work

• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• Finding k Disjoint Paths in a Directed Planar Graph
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. XI: Circuits on a surface
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Graphs on surfaces
• Induced circuits in planar graphs
• Induced disjoint paths problem in a planar digraph
• Maximal Flow Through a Network
• Non-interfering network flows
• On the Computational Complexity of Combinatorial Problems
• Recognizing Berge graphs
• Rooted routing in the plane
• The complexity of induced minors and related problems
• The disjoint paths problem in quadratic time
• The strong perfect graph theorem

Cited in

(21)

• scientific article; zbMATH DE number 3858436 (Why is no real title available?)
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• Graph editing to a fixed target
• The Induced Disjoint Paths Problem
• LINEAR-TIME ALGORITHMS FOR DISJOINT TWO-FACE PATHS PROBLEMS IN PLANAR GRAPHS
• A near-linear-time algorithm for computing replacement paths in planar directed graphs
• Combing a Linkage in an Annulus
• Induced disjoint paths in claw-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Finding a shortest even hole in polynomial time
• Induced disjoint paths problem in a planar digraph
• Parameterizing path partitions
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Few induced disjoint paths for \(H\)-free graphs
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• Algorithms for finding an induced cycle in planar graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Few induced disjoint paths for \(H\)-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• An exponential time parameterized algorithm for planar disjoint paths

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)