Access Restriction

Author Coudert, David ♦ Mazauric, Dorian ♦ Nisse, Nicolas
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Graph ♦ Branch-and-bound ♦ Directed pathwidth ♦ Pathwidth ♦ Vertex separation
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 article, 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 nontrivial techniques to reduce the size of the input graph (preprocessing) 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 (⩽ 10min 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 that generalizes the notion of pathwidth to digraphs.
Description Author Affiliation: Inria, Sophia Antipolis Cedex, France (Coudert, David; Mazauric, Dorian; Nisse, Nicolas)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-01-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 23
Starting Page 1
Ending Page 23

Open content in new tab

   Open content in new tab
Source: ACM Digital Library