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

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

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)

Cites Work

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

Cited In (4)

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

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)