Induced disjoint paths problem in a planar digraph

DOI10.1016/j.dam.2009.06.020zbMath1213.05116OpenAlexW2012799621MaRDI QIDQ967379

Yusuke Kobayashi

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.06.020

zbMATH Keywords

induced subgraphdisjoint pathsplanar digraph

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

Metric and Distributed On-Line Algorithm for Minimizing Routing Interference in Wireless Sensor Networks ⋮ DOAMI: a distributed on-line algorithm to minimize interference for routing in wireless sensor networks ⋮ A linear time algorithm for the induced disjoint paths problem in planar graphs ⋮ Finding multiple induced disjoint paths in general graphs ⋮ Finding an induced subdivision of a digraph ⋮ Algorithms for finding an induced cycle in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• The strong perfect graph theorem
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• On the complexity of testing for odd holes and induced odd paths
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• The Induced Disjoint Paths Problem
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Finding k Disjoint Paths in a Directed Planar Graph

This page was built for publication: Induced disjoint paths problem in a planar digraph