標題: On computing the minimum feedback vertex set of a directed graph by contraction operations
作者: Lin, HM
Jou, JY
電子工程學系及電子研究所
Department of Electronics Engineering and Institute of Electronics
關鍵字: algorithm;branch and bound;design for testability;graph theory;minimum feedback vertex set;partial scan
公開日期: 1-Mar-2000
摘要: 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
期刊: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
Volume: 19
Issue: 3
起始頁: 295
結束頁: 307
Appears in Collections:Articles


Files in This Item:

  1. 000086706500002.pdf