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.
Type de document :
Communication dans un congrès
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

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455353
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 11:00:13
Dernière modification le : mercredi 29 novembre 2017 - 10:26:31
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:13:21

Fichier

fiala.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

47