The k-in-a-path problem for claw-free graphs - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2010

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.

Domains

Discrete Mathematics [cs.DM] Data Structures and Algorithms [cs.DS]
Fichier principal
Vignette du fichier
fiala.pdf (215.32 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Publications Loria  : Connect in order to contact the contributor

https://inria.hal.science/inria-00455353

Submitted on : Wednesday, February 10, 2010-11:00:13 AM

Last modification on : Sunday, January 14, 2024-11:50:06 PM

Long-term archiving on: Friday, June 18, 2010-6:13:21 PM

Download

Dates and versions

inria-00455353 , version 1 (10-02-2010)

Identifiers

  • HAL Id : inria-00455353 , version 1

Cite

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 XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

STACS2010 TDS-MACS
85 View
195 Download

Share

Gmail Facebook X LinkedIn More