The Induced Disjoint Paths Problem

DOI10.1007/978-3-540-68891-4_4MaRDI QIDQ3503839zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Yusuke Kobayashi

Publication date 10 June 2008

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-68891-4_4

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Induced disjoint paths problem in a planar digraph
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Finding multiple induced disjoint paths in general graphs
• The disjoint shortest paths problem
• scientific article; zbMATH DE number 4191702

Cites work

• 2-linked graphs
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Detecting even holes
• Disjoint paths in graphs
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs. I: Decomposition theorem
• 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
• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• On the complexity of testing for odd holes and induced odd paths
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Computational Complexity of Combinatorial Problems
• Recognizing Berge graphs
• Rooted routing in the plane
• The complexity of induced minors and related problems
• The directed subgraph homeomorphism problem
• The strong perfect graph theorem

Cited in

(31)

• General vertex disjoint paths in series-parallel graphs
• Subexponential algorithms for partial cover problems
• Finding multiple induced disjoint paths in general graphs
• Finding an induced path that is not a shortest path
• Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
• Mim-width. I. Induced path problems
• The \(k\)-in-a-path problem for claw-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Vertex disjoint paths for dispatching in railways
• Induced disjoint paths in circular-arc graphs in linear time
• BFS Solution for Disjoint Paths in P Systems
• Tight bounds for linkages in planar graphs
• Irrelevant vertices for the planar disjoint paths problem
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• scientific article; zbMATH DE number 475588 (Why is no real title available?)
• Confronting intractability via parameters
• Edge-disjoint paths in digraphs with bounded independence number
• Modification to Planarity is Fixed Parameter Tractable
• The Directed Disjoint Shortest Paths Problem
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• An exact characterization of tractable demand patterns for maximum disjoint path problems
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• The widestk-set of disjoint paths problem
• Combing a Linkage in an Annulus
• Algorithms for finding an induced cycle in planar graphs
• Path partitions of phylogenetic networks
• A counterexample to the coarse Menger conjecture
• Connectivity-preserving minimum separator in AT-free graphs
• Induced packing of odd cycles in planar graphs
• Induced disjoint paths problem in a planar digraph

This page was built for publication: The Induced Disjoint Paths Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503839)