The k-in-a-path problem for claw-free graphs

DOI10.1007/S00453-010-9468-ZMaRDI QIDQ2428671zbMATH OpenOpenAlexFDO

Authors Bernard Lidický, Daniël Paulusma, Jiří Fiala, Marcin Kamiński

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

claw-free graphpolynomial time algorithminduced path

Mathematics Subject Classification ID

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

Recommendations

• The \(k\)-in-a-path problem for claw-free graphs
• Induced disjoint paths in claw-free graphs
• Induced disjoint paths in claw-free graphs
• Finding induced paths of given parity in claw-free graphs
• Finding induced paths of given parity in claw-free graphs

Cites work

• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Chordless paths through three vertices
• Claw-free graphs---a survey
• Detecting even holes
• Finding induced paths of given parity in claw-free graphs
• Finding induced trees
• Graph minors. XIII: The disjoint paths problem
• Incidence matrices and interval graphs
• Induced Packing of Odd Cycles in a Planar Graph
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On the Computational Complexity of Combinatorial Problems
• On the complexity of testing for odd holes and induced odd paths
• Recognizing claw-free perfect graphs
• Smallest odd holes in claw-free graphs (extended abstract)
• The Induced Disjoint Paths Problem
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The four-in-a-tree problem in triangle-free graphs
• The strong perfect graph theorem
• The structure of claw-free graphs
• The three-in-a-tree problem

Cited in

(24)

• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Vertex elimination orderings for hereditary graph classes
• The \(k\)-in-a-path problem for claw-free graphs
• Finding a smallest odd hole in a claw-free graph using global structure
• Finding induced paths of given parity in claw-free graphs
• Clique or hole in claw-free graphs
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• Finding induced paths of given parity in claw-free graphs
• The \(k\)-in-a-tree problem for chordal graphs
• Mim-width. I. Induced path problems
• FPT and kernelization algorithms for the induced tree problem
• Detecting fixed patterns in chordal graphs in polynomial time
• Induced disjoint paths in claw-free graphs
• scientific article; zbMATH DE number 6302876 (Why is no real title available?)
• Induced disjoint paths in claw-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
• The path partition conjecture is true for claw-free graphs
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Few induced disjoint paths for \(H\)-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Few induced disjoint paths for \(H\)-free graphs
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428671)