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

Please wait, while we are loading the content...

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

Content Provider	ACM Digital Library
Author	Coudert, David Mazauric, Dorian Nisse, Nicolas
Copyright Year	2016
Description	Author Affiliation: Inria, Sophia Antipolis Cedex, France (Coudert, David; Mazauric, Dorian; Nisse, Nicolas)
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.
Starting Page	1
Ending Page	23
Page Count	23
File Format	PDF
ISSN	10846654
e-ISSN	10846654
DOI	10.1145/2851494
Journal	Journal of Experimental Algorithmics (JEA)
Volume Number	21
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Graph Branch-and-bound Directed pathwidth Pathwidth Vertex separation
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Computing Directed Pathwidth in $$O(1.89^{n})$$ Time

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion

Pathwidth of outerplanar graphs

A Preliminary Evaluation of the Critical Path Method for Scheduling Tasks on Multiprocessor Systems

Experimental evaluation of a branch and bound algorithm for computing (2014).

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

Similar Documents

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Computing Directed Pathwidth in $$O(1.89^{n})$$ Time

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion

Pathwidth of outerplanar graphs

A Preliminary Evaluation of the Critical Path Method for Scheduling Tasks on Multiprocessor Systems

Experimental evaluation of a branch and bound algorithm for computing (2014).

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