Skip to Main content Skip to Navigation
Conference papers

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

Jiří Fiala 1, 2, * Marcin Kamiński 3 Bernard Lidický 1, 2 Daniël Paulusma 4
* Corresponding author
1 ITI - Institute for Theoretical Computer Science
2 Faculty of Mathematics and Physics, DIMATIA
3 ULB - Département d'Informatique [Bruxelles]
4 Department of Computer Science
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.
Keywords : induced path claw-free graph polynomial-time algorithm
Document type :
Conference papers
Complete list of metadata

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, June 4, 2020 - 10:40:07 AM
Long-term archiving on: : Friday, June 18, 2010 - 6:13:21 PM

File

Vignette du document
fiala.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455353, version 1

Collections

STACS2010 | TDS-MACS

Citation

Jiří Fiala, Marcin Kamiński, Bernard Lidický, Daniël Paulusma. The k-in-a-path problem for claw-free graphs. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.371-382. ⟨inria-00455353⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

210

Files downloads

278

 

Contact                    Legal Notice                    Personal Data