Paper Info
Title
Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm.
Abstract
The BT algorithm of Bouchitté and Todinca based on enumerating potential maximal cliques, originally proposed for the treewidth and minimum fill-in problems, yields improved exact exponential-time algorithms for various graph optimization problems related to optimal triangulations. While the BT algorithm has received significant attention in terms of theoretical analysis, less attention has been paid on engineering efficient implementations of the algorithm for different problems and thereby on empirical studies on its effectiveness in practice. In this work, we provide an experimental evaluation of an implementation of the BT algorithm, based on our second-place winning entry in the 2nd Parameterized Algorithms and Computational Experiments Challenge (PACE 2017), extended to several related graph problems: treewidth, minimum fill-in, generalized and fractional hypertreewidth, and the total table size problem. Instead of focusing on problem-specific optimization of BT for a particular problem, our focus in this work is on studying the applicability of BT more generally to a range of problems. Based on the results, we conclude that an efficient implementation of the BT algorithm yields an empirically competitive approach to each of the considered problems when compared to available implementations of alternative problem-specific algorithmic approaches.
Year
DOI
Venue
2019
10.1145/3301297
Journal of Experimental Algorithmics
Keywords
DocType
Volume
Bouchitté-Todinca algorithm,Potential maximal cliques,chordal completion,empirical evaluation,fractional hypertreewidth,generalized hypertreewidth,minimum fill-in,total table size,treewidth
Journal
24
Issue
ISSN
Citations 
1
1084-6654
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Tuukka Korhonen103.38
Jeremias Berg2417.87
Matti Järvisalo358151.00