Tag Archives: algorithm implementation

A new publication

Our publication Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm has been accepted for publication in the ACM Journal of Experimental Algorithmics. The article is currently in press, let me know if you are interested in reading it.  I am the second author on this publication, with Tuukka Korhonen as the first and my PhD advisor  Matti Järvisalo as the third.

The paper reports on an experimental evaluation of the so called Bouchitté-Todinca (BT) Algorithm for computing various graph parameters, including the treewidth and minimum fill of a graph. While the algorithm is the theoretically best known one for computing most of these parameters, there has not been many practical evaluations of it, probably due to it being quite complicated to implement in practice. In this paper we provide an experimental evaluation of Tuukkas implementation that took second place in the minimum fill in track of the  2017 PACE challenge on 5 different graph problems. In the paper we show that Tuukas implementation of the BT algorithm is competitive with many previously proposed, problem specific algorithms, on all of the problems we consider. My role in this paper was to familiarize myself with and write about the theoretical foundations of the algorithm as well as provide input on what kind of experiments we should run. I liked working on this project as it allowed me to familiarize myself with something else than constraint programming.

Thanks to both Tuukka and Matti for their work in making this happen.