A Polynomial Kernel For Multicut In Trees

Nicolas Bousquet 1 Jean Daligault 2 Stéphan Thomassé 3 Anders Yeo 4
1 ENS Cachan - École normale supérieure - Cachan
2 LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 Department of Computer Science
Abstract : The MULTICUT IN TREES problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer k, whether there exists a set of k edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer. They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows. We show that MULTICUT IN TREES has a polynomial kernel.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. STACS'2009: 26th International Symposium on Theoretical Aspects of Computer Science, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.183-194, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées
https://hal.inria.fr/inria-00359171
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 10:47:34
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mardi 8 juin 2010 - 21:57:11

Fichiers

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

Identifiants

  • HAL Id : inria-00359171, version 1
  • ARXIV : 0902.1047

Collections

STACS2009 | ALGCO | LIRMM | ENS-CACHAN | TDS-MACS | MIPS | UNIV-MONTPELLIER

Citation

Nicolas Bousquet, Jean Daligault, Stéphan Thomassé, Anders Yeo. A Polynomial Kernel For Multicut In Trees. Susanne Albers and Jean-Yves Marion. STACS'2009: 26th International Symposium on Theoretical Aspects of Computer Science, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.183-194, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359171〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

189

Contact


archive-ouverte@inria.fr