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

DOI10.1007/s00453-010-9468-zzbMath1236.68088MaRDI 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 algorithm; claw-free graph; induced path

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Induced Disjoint Paths in Claw-Free Graphs, Few induced disjoint paths for \(H\)-free graphs, 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, Induced disjoint paths in AT-free graphs, Few induced disjoint paths for \(H\)-free graphs, Mim-width. I. Induced path problems, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Detecting fixed patterns in chordal graphs in polynomial time, Vertex elimination orderings for hereditary graph classes, Induced disjoint paths in circular-arc graphs in linear time, FPT and kernelization algorithms for the induced tree problem

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