Computing minimum feedback vertex sets by contraction operations and its applications on CAD

Hen Ming Lin, Jing Yang Jou

Research output: Contribution to conferencePaperpeer-review

11 Scopus citations


Finding the minimum feedback vertex set (MFVS) in a graph is an important problem for a variety of 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, 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. We have implemented our algorithms and applied them to solving the partial scan problem in ISCAS89 benchmarks. The experimental results show that for all ISCAS89 benchmarks our exact algorithm can find the exact cutsets in less than 3 seconds (CPU time) on SUN-Ultrall workstation.

Original languageEnglish
Number of pages6
StatePublished - 1999
EventInternational Conference on Computer Design (ICCD'99) - Austin, TX, USA
Duration: 10 Oct 199913 Oct 1999


ConferenceInternational Conference on Computer Design (ICCD'99)
CityAustin, TX, USA


Dive into the research topics of 'Computing minimum feedback vertex sets by contraction operations and its applications on CAD'. Together they form a unique fingerprint.

Cite this