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

Abstract : Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial time on claw-free graphs, when k is not part of the input but an arbitrarily fixed integer.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.371-382, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00455353
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 11:00:13 AM
Last modification on : Thursday, July 19, 2018 - 4:58:09 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 6:13:21 PM

File

fiala.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455353, version 1

Collections

Citation

Jiří Fiala, Marcin Kamiński, Bernard Lidický, Daniël Paulusma. The k-in-a-path problem for claw-free graphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.371-382, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455353〉

Share

Metrics

Record views

159

Files downloads

55