A revisit of the scheme for computing treewidth and minimum fill-in

作者：Furuse Masanobu; Yamazaki Koichi^*

来源：Theoretical Computer Science, 2014, 531: 66-76.

DOI：10.1016/j.tcs.2014.03.013

• Minimal separator
• Potential maximal clique
• Treewidth
• Minimum fill-in

In this paper, we reformulate the scheme introduced by Bouchitte and Todinca in [1], which computes treewidth and minimum fill-in of a graph using a dynamic programming approach. We will call the scheme BT 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.

• 出版日期2014-4-24