Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

David Coudert 1 Dorian Mazauric 2 Nicolas Nisse 1, 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Les décompositions en chemin de graphes sont très importants pour la conception d'algorithmes de programmation dynamique pour résoudre de nombreux problèmes NP-difficiles. Calculer la pathwidth et la décomposition en chemin correspondante sont donc d'un grand intérêt tant d'un point de vue théorique que pratique. Dans ce papier, nous proposons un algorithme de Branch and Bound qui calcule la pathwidth et une décomposition. Notre contribution principale réside dans les techniques que nous prouvons pour réduire la taille du graphe donné en entrée (prétraitement) et réduire la taille de l'espace d'exploration de la phase de recherche de l'algorithme. Nous évaluons expérimentalement notre algorithme en le comparant aux algorithmes proposés dans la littérature. Les simulations montrent que notre algorithme apporte un gain significatif par rapport aux algorithmes existants. Il est capable de calculer la valeur exacte de la pathwidth de tout graphe composé d'au plus 60 sommets en un temps raisonnable (moins de 10 minutes). De plus, notre algorithme montre de bonnes performances lorsqu'il est utilisé en heuristique (c'est-à-dire lorsqu'il retourne le meilleur résultat trouvé en un temps donné). Notre algorithme n'est pas spécifique au graphes non orientés car il permet de calculer la vertex-separation des digraphes (qui coïncide avec la pathwidth dans le cas des graphes non orientés).
Type de document :
Communication dans un congrès
13th International Symposium on Experimental Algorithms, 2014, Copenhagen, Denmark. 8504, pp.46-58, 2014, Lecture Notes in Computer Science


https://hal.inria.fr/hal-00966851
Contributeur : Nicolas Nisse <>
Soumis le : jeudi 27 mars 2014 - 14:29:13
Dernière modification le : mardi 21 février 2017 - 01:09:46
Document(s) archivé(s) le : vendredi 27 juin 2014 - 11:45:22

Fichier

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

Identifiants

  • HAL Id : hal-00966851, version 1

Collections

Citation

David Coudert, Dorian Mazauric, Nicolas Nisse. Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth. 13th International Symposium on Experimental Algorithms, 2014, Copenhagen, Denmark. 8504, pp.46-58, 2014, Lecture Notes in Computer Science. <hal-00966851>

Partager

Métriques

Consultations de
la notice

372

Téléchargements du document

212