An optimal algorithm for cycle breaking in directed graphs
Tóm tắt
This paper describes an exact algorithm for the identification of a minimal 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 solutions were found. In other cases, the optimality of the solution could not be established for all circuits. By using the proposed algorithm we obtained the optimum results for all the circuits in a relatively short CPU time.
Tài liệu tham khảo
E.L. Lloyd and M.L. Soffa, “On locating minimum feedback vertex sets,”Journal of Computer and System Science, Vol. 37, pp. 292–311, 1988.
G.W. Smith and R.B. Walford, “The identification of a minimal feedback vertex set of a directed graph,”IEEE Transactions on Circuits and Systems, Vol. CAS-22, No. 1 pp. 9–14, January 1975).
D.H. Younger, “Minimum feedback are set for a directed graph,”IEEE Transactions on Circuit Theory, Vol. CT-10, pp. 238–245, June 1963.
R.M. Karp, “Reducibility between combinatorial problems,”Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (Eds.), New York: Plenum Press, pp. 85–103, 1972.
A. Miczo,Digital Logic Testing and Simulations, New York: Harper and Row, 1986.
D.H. Lee and S.M. Reddy, “On determining scan flip-flops in partial-scan designs,” inProc. of the International Conference on Computer-Aided Design, pp. 322–325, 1990.
H. Levy and D.W. Low, “A contraction algorithm for finding small cycle cutsets,”Journal of Algorithms, pp. 470–493, September 1988.
V. Chickermane, J. Lee, and J.H. Patel, “Design for testability using architectural description,” inProc. of the International Test Conference, pp. 752–761, 1992.
F. Brglez, D. Bryan, and K. Kozminski, “Combinational profiles of sequential benchmark circuits,” inProc. of the IEEE International Symposium on Circuits and Systems, pp. 1929–1934, 1989.
K.-T. Cheng and V.D. Agrawal, “A partial scan method for sequential circuits with feedback,”IEEE Transactions on Computers, Vol. 39, No. 4, pp. 544–548, April 1990.
T. Orenstein, MSC Thesis. Dept. of Comp. Science, Technion, February 1992.
R. Tarjan, “Depth-first search and linear graph algorithms,”SIAM J. Comput, Vol. 1, No. 2, pp. 146–160, June 1972.