Finding induced paths of given parity in claw-free graphs

DOI10.1007/S00453-010-9470-5zbMATH Open1236.68101OpenAlexW2116786738MaRDI QIDQ2428656FDOQ2428656

Authors Pim Van 't Hof, Daniël Paulusma, Marcin Kamiński 

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/9019/1/9019.pdf

zbMATH Keywords

claw-free graphpolynomial-time algorithminduced pathparity path

Mathematics Subject Classification ID

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

Recommendations

• Finding induced paths of given parity in claw-free graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• Even pairs in claw-free perfect graphs
• The \(k\)-in-a-path problem for claw-free graphs
• The \(k\)-in-a-path problem for claw-free graphs

Cites work

• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• A description of claw-free perfect graphs
• A linear algorithm for the group path problem on chordal graphs
• A new property of critical imperfect graphs and some consequences
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms on clique separable graphs
• Decomposition by clique separators
• Detecting even holes
• Efficient reduction for path problems on circular-arc graphs
• Even and odd pairs in comparability and in \(P_4\)-comparability graphs
• Even pairs
• Even pairs in claw-free perfect graphs
• Finding induced trees
• Incidence matrices and interval graphs
• Modularity of cycles and paths in graphs
• On the complexity of finding even pairs in planar perfect graphs
• On the complexity of testing for odd holes and induced odd paths
• Path parity and perfection
• Recognizing Berge graphs
• Recognizing Perfect 2-Split Graphs
• Recognizing claw-free perfect graphs
• Smallest odd holes in claw-free graphs (extended abstract)
• Stable set bonding in perfect graphs and parity graphs
• The Use of Linear Graphs in Gauss Elimination
• The even-path problem for graphs and digraphs
• The parity path problem on some subclasses of perfect graphs
• The strong perfect graph theorem
• The three-in-a-tree problem
• Three-colourable perfect graphs without even pairs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

Cited in

(5)

• The \(k\)-in-a-path problem for claw-free graphs
• Finding induced paths of given parity in claw-free graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• Claw-free \(t\)-perfect graphs can be recognized in polynomial time

This page was built for publication: Finding induced paths of given parity in claw-free graphs

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