TreeWidthSolver.jl is a Julia package for solving the minimal treewidth and the corresponding tree decomposition of graphs. Currently we implemented the Bouchitte-Todinca algorithm12, which is a dynamic programming algorithm for solving the exact minimal treewidth problem of graphs. This package is used as a bacakend of OMEinsumContractionOrders.jl for finding the optimal tensor network contraction order.
For more details about this pacakage please see the docs, and please refer to this blog for more about the algorithm we implemented.
Footnotes
-
Bouchitté, Vincent, and Ioan Todinca. “Treewidth and Minimum Fill-in: Grouping the Minimal Separators.” SIAM Journal on Computing 31, no. 1 (January 2001): 212–32. https://doi.org/10.1137/S0097539799359683 ↩
-
Korhonen, Tuukka, Jeremias Berg, and Matti Järvisalo. “Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté--Todinca Algorithm.” ACM Journal of Experimental Algorithmics 24 (December 17, 2019): 1–19. https://doi.org/10.1145/3301297. ↩