An Algorithm for the Exact Treedepth Problem

04/19/2020
by   James Trimble, et al.
0

We present a novel algorithm for the minimum-depth elimination tree problem, which is equivalent to the optimal treedepth decomposition problem. Our algorithm makes use of two cheaply-computed lower bound functions to prune the search tree, along with symmetry-breaking and domination rules. We present an empirical study showing that the algorithm outperforms the current state-of-the-art solver (which is based on a SAT encoding) by orders of magnitude on a range of graph classes.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset