完整後設資料紀錄
DC 欄位語言
dc.contributor.authorLin, HMen_US
dc.contributor.authorJou, JYen_US
dc.date.accessioned2014-12-08T15:45:37Z-
dc.date.available2014-12-08T15:45:37Z-
dc.date.issued2000-03-01en_US
dc.identifier.issn0278-0070en_US
dc.identifier.urihttp://dx.doi.org/10.1109/43.833199en_US
dc.identifier.urihttp://hdl.handle.net/11536/30688-
dc.description.abstractFinding 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.en_US
dc.language.isoen_USen_US
dc.subjectalgorithmen_US
dc.subjectbranch and bounden_US
dc.subjectdesign for testabilityen_US
dc.subjectgraph theoryen_US
dc.subjectminimum feedback vertex seten_US
dc.subjectpartial scanen_US
dc.titleOn computing the minimum feedback vertex set of a directed graph by contraction operationsen_US
dc.typeArticleen_US
dc.identifier.doi10.1109/43.833199en_US
dc.identifier.journalIEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMSen_US
dc.citation.volume19en_US
dc.citation.issue3en_US
dc.citation.spage295en_US
dc.citation.epage307en_US
dc.contributor.department電子工程學系及電子研究所zh_TW
dc.contributor.departmentDepartment of Electronics Engineering and Institute of Electronicsen_US
dc.identifier.wosnumberWOS:000086706500002-
dc.citation.woscount7-
顯示於類別:期刊論文


文件中的檔案:

  1. 000086706500002.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。