Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth and Directed Pathwidth

David Coudert 1 Dorian Mazauric 2 Nicolas Nisse 1
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
2 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Path-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path-decomposition of graphs has both a theoretical and practical interest. In this paper, we design a Branch and Bound algorithm that computes the exact pathwidth of graphs and a corresponding path-decomposition. Our main contribution consists of several non-trivial techniques to reduce the size of the input graph (pre-processing) and to cut the exploration space during the search phase of the algorithm. We evaluate experimentally our algorithm by comparing it to existing algorithms of the literature. It appears from the simulations that our algorithm offers a significant gain with respect to previous work. In particular, it is able to compute the exact pathwidth of any graph with less than 60 nodes in a reasonable running-time (≤ 10 minutes on a standard laptop). Moreover, our algorithm achieves good performance when used as a heuristic (i.e., when returning best result found within bounded time-limit). Our algorithm is not restricted to undirected graphs since it actually computes the directed pathwidth which generalizes the notion of pathwidth to digraphs.
Type de document :
Article dans une revue
ACM Journal of Experimental Algorithmics, 2016, 21 (1), pp.23. <10.1145/2851494>
Liste complète des métadonnées


https://hal.inria.fr/hal-01266496
Contributeur : David Coudert <>
Soumis le : mardi 2 février 2016 - 18:25:09
Dernière modification le : vendredi 5 février 2016 - 01:13:11
Document(s) archivé(s) le : samedi 12 novembre 2016 - 03:51:23

Fichier

babpw-20151120.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Dorian Mazauric, Nicolas Nisse. Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth and Directed Pathwidth. ACM Journal of Experimental Algorithmics, 2016, 21 (1), pp.23. <10.1145/2851494>. <hal-01266496>

Partager

Métriques

Consultations de
la notice

159

Téléchargements du document

92