A revisit of the scheme for computing treewidth and minimum fill-in
A revisit of the scheme for computing treewidth and minimum fill-in
复制标题
重新审视计算树宽和最小填充的方案
DOI：
10.1016/j.tcs.2014.03.013
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
Koichi Yamazaki
中科院分区：
文献类型：
--
作者：
Masanobu Furuse;Koichi Yamazaki
本文将Bouchitté和Todinca在文献[1]中提出的用动态规划方法计算图的树宽和最小填充的方案进行了改进。我们将该方案称为BT方案。虽然BT方案最初是为计算树宽和最小填充而设计的，但它可以用于计算根据最小三角剖分定义的其他图参数。在本文中，我们重新制定的BT计划，使其适用于计算其他图参数定义的最小三角剖分，并给出了其他图参数的例子。
In this paper, we reformulate the scheme introduced by Bouchitté and Todinca in [1], which computes treewidth and minimum fill-in of a graph using a dynamic programming approach. We will call the schemeBT scheme. Although BT scheme was originally designed for computing treewidth and minimum fill-in, it can be used for computing other graph parameters defined in terms of minimal triangulation. In this paper, we reformulate BT scheme so that it works for computing other graph parameters defined in terms of minimal triangulation, and give examples of other graph parameters.