The Induced Disjoint Paths Problem
From MaRDI portal
Publication:3503839
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
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
