Induced Disjoint Paths in Claw-Free Graphs

DOI10.1137/140963200zbMath1311.05090arXiv1202.4419OpenAlexW2571021594MaRDI QIDQ5251566

Daniël Paulusma, Petr A. Golovach, Erik Jan van Leeuwen

Publication date: 20 May 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.4419

zbMATH Keywords

claw-free graphsparameterized complexityinduced disjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Induced disjoint paths in AT-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Parameterized complexity of induced graph matching on claw-free graphs
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• Kernel bounds for disjoint cycles and disjoint paths
• The three-in-a-tree problem
• Clique or hole in claw-free graphs
• Containment relations in split graphs
• Chordless paths through three vertices
• The four-in-a-tree problem in triangle-free graphs
• Claw-free graphs. V. Global structure
• Finding induced trees
• On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Induced circuits in planar graphs
• The complexity of induced minors and related problems
• On a closure concept in claw-free graphs
• Graph minors. XIII: The disjoint paths problem
• Induced disjoint paths in AT-free graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Detecting induced star-like minors in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• Induced Disjoint Paths in Claw-Free Graphs
• Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
• Domination When the Stars Are Out
• Bounding χ in terms of ω and Δ for quasi-line graphs
• On the Computational Complexity of Combinatorial Problems
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Finding topological subgraphs is fixed-parameter tractable
• Detecting induced subgraphs

This page was built for publication: Induced Disjoint Paths in Claw-Free Graphs