The Induced Disjoint Paths Problem

DOI10.1007/978-3-540-68891-4_4zbMath1143.90379OpenAlexW1604132306MaRDI QIDQ3503839

Yusuke Kobayashi, Ken-ichi Kawarabayashi

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

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

Related Items

Irrelevant vertices for the planar disjoint paths problem, Mim-width. I. Induced path problems, Combing a Linkage in an Annulus, The \(k\)-in-a-path problem for claw-free graphs, Subexponential algorithms for partial cover problems, Finding multiple induced disjoint paths in general graphs, Confronting intractability via parameters, Algorithms for finding an induced cycle in planar graphs, Tight Bounds for Linkages in Planar Graphs, Induced disjoint paths problem in a planar digraph, Unnamed Item, Modification to Planarity is Fixed Parameter Tractable, Induced packing of odd cycles in planar graphs, Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XXII. Irrelevant vertices in linkage problems
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• The strong perfect graph theorem
• Graph minors. VII: Disjoint paths on a surface
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• On the complexity of testing for odd holes and induced odd paths
• Graph minors. XI: Circuits on a surface
• Rooted routing in the plane
• The complexity of induced minors and related problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• Recognizing Berge graphs
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• 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
• Detecting even holes