A unified FPT Algorithm for Width of Partition Functions

Pascal Berthomé 1 Nicolas Nisse 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : During the last decades, several polynomial-time algorithms have been designed that decide if a graph has treewidth (resp., pathwidth, branchwidth, etc.) at most $k$, where $k$ is a fixed parameter. Amini {\it et al.} (to appear in SIAM J. Discrete Maths.) use the notions of partitioning-trees and partition functions as a generalized view of classical decompositions of graphs, namely tree-decomposition, path-decomposition, branch-decomposition, etc. In this paper, we propose a set of simple sufficient conditions on a partition function $\Phi$, that ensures the existence of a linear-time explicit algorithm deciding if a set $A$ has $\Phi$-width at most $k$ ($k$ fixed). In particular, the algorithm we propose unifies the existing algorithms for treewidth, pathwidth, linearwidth, branchwidth, carvingwidth and cutwidth. It also provides the first Fixed Parameter Tractable linear-time algorithm deciding if the $q$-branched treewidth, defined by Fomin {\it et al.} (Algorithmica 2007), of a graph is at most $k$ ($k$ and $q$ are fixed). Our decision algorithm can be turned into a constructive one by following the ideas of Bodlaender and Kloks (J. of Alg. 1996).
Type de document :
Rapport
[Research Report] RR-6646, INRIA. 2008, pp.36
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00321766
Contributeur : Nicolas Nisse <>
Soumis le : lundi 15 septembre 2008 - 18:39:29
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : jeudi 3 juin 2010 - 19:50:54

Fichier

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

Identifiants

  • HAL Id : inria-00321766, version 1

Citation

Pascal Berthomé, Nicolas Nisse. A unified FPT Algorithm for Width of Partition Functions. [Research Report] RR-6646, INRIA. 2008, pp.36. 〈inria-00321766〉

Partager

Métriques

Consultations de la notice

357

Téléchargements de fichiers

102