An Unified FPT Algorithm for Width of Partition Functions

Résumé : Au cours de ces dernières années, plusieurs algorithmes polynomiaux ont été conçus pour décider si un graphe a largeur arborescente (resp., largeur en chemin, branch-width, etc) au plus k, où k est un paramètre fixe. Amini et al. (Discrete Mathematics'09) ont utilisé les notions d'arbres de partition et de fonctions de partition comme une vision généralisée des décompositions des graphes classiques, à savoir la décomposition arborescente, la décomposition en chemin, la décomposition en branche, etc. Dans cet article, nous proposons un ensemble de conditions sur une fonction de partition Φ, qui assure l'existence d'un algorithme explicite en temps linéaire pour décider si un ensemble A a Φ-largeur au plus k (oú k est fixé). En particulier, l'algorithme que nous proposons unifie les algorithmes existants pour la largeur arborescente, largeur en chemin, la largeur linéaire, la largeur de branche, cut-width et carving-width. Il est également le premier algorithme FPT pour décider si la largeur arborescente q-ramifié, définie par Fomin et al. (Algorithmica'09), d'un graphe est au plus k (k et q sont fixées). De plus, l'algorithme est capable de décider si la largeur arborescente spéciale, définie par Courcelle (FSTTCS'10), est plus k, où k est un paramètre fixé. Notre algorithme de décision peut être transformé en un algorithme constructif en suivant les idées de Bodlaender et Kloks (J. of Alg., 1996).
Type de document :
Rapport
[Research Report] RR-8372, INRIA. 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00865575
Contributeur : Ronan Pardo Soares <>
Soumis le : lundi 30 septembre 2013 - 11:46:57
Dernière modification le : mardi 13 décembre 2016 - 15:44:55
Document(s) archivé(s) le : vendredi 7 avril 2017 - 04:22:34

Fichier

RR-8372.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00865575, version 2

Citation

Pascal Berthomé, Tom Bouvier, Frédéric Mazoit, Nicolas Nisse, Ronan Pardo Soares. An Unified FPT Algorithm for Width of Partition Functions. [Research Report] RR-8372, INRIA. 2013. <hal-00865575v2>

Partager

Métriques

Consultations de
la notice

473

Téléchargements du document

197