The \(k\)-in-a-path problem for claw-free graphs

DOI10.1007/s00453-010-9468-zzbMath1236.68088OpenAlexW2126486668MaRDI QIDQ2428671

Bernard Lidický, Daniël Paulusma, Marcin Kaminski, Jiří Fiala

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9468-z

zbMATH Keywords

polynomial time algorithmclaw-free graphinduced path

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Induced disjoint paths in circular-arc graphs in linear time ⋮ Mim-width. I. Induced path problems ⋮ 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 ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Unnamed Item ⋮ 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
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The three-in-a-tree problem
• Chordless paths through three vertices
• The four-in-a-tree problem in triangle-free graphs
• The strong perfect graph theorem
• Finding induced trees
• Recognizing claw-free perfect graphs
• On the complexity of testing for odd holes and induced odd paths
• Claw-free graphs---a survey
• Graph minors. XIII: The disjoint paths problem
• Incidence matrices and interval graphs
• The Induced Disjoint Paths Problem
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Induced Packing of Odd Cycles in a Planar Graph
• On the Computational Complexity of Combinatorial Problems
• Detecting even holes
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Smallest Odd Holes in Claw-Free Graphs (Extended Abstract)
• Finding Induced Paths of Given Parity in Claw-Free Graphs
• Detecting induced subgraphs

This page was built for publication: The \(k\)-in-a-path problem for claw-free graphs