An optimal algorithm for cycle breaking in directed graphs
| Autor: | Zvi Kohavi, Tatiana Orenstein, Irith Pomeranz |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
Vertex (graph theory)
Graph partition Directed graph Feedback arc set law.invention Computer Science::Hardware Architecture Computer Science::Emerging Technologies law Line graph Hardware_INTEGRATEDCIRCUITS Graph (abstract data type) Feedback vertex set Electrical and Electronic Engineering Algorithm Hardware_LOGICDESIGN Mathematics Moral graph |
| Zdroj: | Journal of Electronic Testing. 7:71-81 |
| ISSN: | 1573-0727 0923-8174 |
| DOI: | 10.1007/bf00993315 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink