Finding induced paths of given parity in claw-free graphs

DOI10.1007/s00453-010-9470-5zbMath1236.68101MaRDI QIDQ2428656

Daniël Paulusma, Marcin Kaminski, Pim van 't Hof

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 graph; polynomial-time algorithm; induced path; parity path

Mathematics Subject Classification ID

05C38: Paths and cycles

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

05C85: Graph algorithms (graph-theoretic aspects)