Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436441 | Theoretical Computer Science | 2014 | 11 Pages |
Abstract
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 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Masanobu Furuse, Koichi Yamazaki,