Computing Treewidth via Exact and Heuristic Lists of Minimal Separators
Computing Treewidth via Exact and Heuristic Lists of Minimal Separators
复制标题
通过最小分隔符的精确和启发式列表计算树宽
DOI：
10.1007/978-3-030-34029-2_15
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
HIsao Tamaki
中科院分区：
文献类型：
--
作者：
Ryota Kawasumi;Koujin Takeda;HIsao Tamaki
我们开发了实用有效的算法来计算图 G 的树宽。我们方法的核心是一种新的动态规划算法，给定一个图G、一个正整数k和G的一组最小分隔符，决定G是否具有某种规范形式的宽度至多为k的树分解，该规范形式仅使用最小分隔符，即每对相邻袋的交集所属的意义上。该算法用于显示 on 的下界，设置为最多基数的所有最小分隔符的集合，并显示 kon 的上限，设置为此类最小分隔符的一些（希望是丰富的）集合。将该算法与用于最小分隔符的精确和启发式列表的新算法相结合，我们获得了树宽的精确算法，其性能远远优于以前实现的算法。
We develop practically efficient algorithms for computing the treewidthof a graphG. The core of our approach is a new dynamic programming algorithm which, given a graphG, a positive integerk, and a setof minimal separators ofG, decides ifGhas a tree-decomposition of width at mostkof a certain canonical form that uses minimal separators only from, in the sense that the intersection of every pair of adjacent bags belongs to. This algorithm is used to show a lower bound ofon, settingto be the set of all minimal separators of cardinality at mostkand to show an upper bound ofkon, settingto be some, hopefully rich, set of such minimal separators. Combining this algorithm with new algorithms for exact and heuristic listing of minimal separators, we obtain exact algorithms for treewidth which overwhelmingly outperform previously implemented algorithms.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
International Symposium on Parameterized and Exact Computation
影响因子：
--
作者：
Holger Dell;T. Husfeldt;B. Jansen;P. Kaski;Christian Komusiewicz;Frances A. Rosamond
通讯作者：
Frances A. Rosamond
用于列出图的最小顶点分隔符的空间最优回溯算法
DOI：
10.1016/j.dam.2010.05.013
发表时间：
2010
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Kenshiro Takata
通讯作者：
Kenshiro Takata
影响因子：
1.1
作者：
F. Fomin;Yngve Villanger
通讯作者：
Yngve Villanger
DOI：
--
发表时间：
2004
期刊：
Conference on Uncertainty in Artificial Intelligence
影响因子：
--
作者：
Vibhav Gogate;R. Dechter
通讯作者：
R. Dechter
影响因子：
1
作者：
Tamaki, Hisao
通讯作者：
Tamaki, Hisao