AN OPTIMAL ALGORITHM FOR CYCLE BREAKING IN DIRECTED-GRAPHS

This paper describes an exact algorithm for the identification of a mi nimal feedback vertex set in digital circuits. The proposed algorithm makes use of graph reduction and efficient graph partitioning methods based on local properties of digital circuits. It has been implemented and applied to ISCAS-89 benchmark circuits. Previously, non-optimum s olutions were found. In other cases, the optimality of the solution co uld not be established for all circuits. By using the proposed algorit hm we obtained the optimum results for all the circuits in a relativel y short CPU time.