Title: | On computing the minimum feedback vertex set of a directed graph by contraction operations |
Authors: | Lin, HM Jou, JY 電子工程學系及電子研究所 Department of Electronics Engineering and Institute of Electronics |
Keywords: | algorithm;branch and bound;design for testability;graph theory;minimum feedback vertex set;partial scan |
Issue Date: | 1-Mar-2000 |
Abstract: | Finding the minimum feedback vertex set (MFVS) in a graph is an important problem for a variety of computer-aided design (CAD) applications and graph reduction plays an important role in solving this intractable problem. This paper is largely concerned with three new and powerful reduction operations. Each of these operations defines a new class of graphs, strictly larger than the class of contractible graphs [Levy and Low (1988)], in which the MFVS can be found in polynomial-time complexity. Based on these operations, an exact algorithm run on branch and bound manner is developed. This exact algorithm uses a good heuristic to find out an initial solution and a good bounding strategy to prune the solution space. To demonstrate the efficiency of our algorithms, we have implemented our algorithms and applied them to solving the partial scan problem in ISCAS'89 benchmarks. The experimental results show that if our three new contraction operations are applied, 27 out of 31 circuits in ISCAS'89 benchmarks can be fully reduced. Otherwise, only 12 out of 31 can be fully reduced. Furthermore, for all ISCAS'89 benchmarks our exact algorithm can fmd the exact cutsets in less than 3 s (CPU time) on SUN-UltraII workstation. Therefore, the new contraction operations and our algorithms are demonstrated to be very effective in the partial scan application. |
URI: | http://dx.doi.org/10.1109/43.833199 http://hdl.handle.net/11536/30688 |
ISSN: | 0278-0070 |
DOI: | 10.1109/43.833199 |
Journal: | IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS |
Volume: | 19 |
Issue: | 3 |
Begin Page: | 295 |
End Page: | 307 |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.