Abstract
An optimal algorithm to find the longest simple path in a cyclic combinatorial circuit is proposed. The approach first replaces cycles with matched sub-circuits and then compute the longest simple path of the expanded circuit. The matched sub-circuits are carefully constructed to preserve the path information of the original cyclic combinatorial circuit. The proposed algorithm has exponential time complexity in the worst case. Nevertheless, experimental results demonstrate the feasibility of the proposed algorithm.
Original language | English (US) |
---|---|
Title of host publication | VLSI in Computers and Processors |
Publisher | IEEE |
Pages | 530-535 |
Number of pages | 6 |
State | Published - Dec 1 1998 |
Event | Proceedings of the 1998 IEEE International Conference on Computer Design - Austin, TX, USA Duration: Oct 5 1998 → Oct 7 1998 |
Other
Other | Proceedings of the 1998 IEEE International Conference on Computer Design |
---|---|
City | Austin, TX, USA |
Period | 10/5/98 → 10/7/98 |