במעגל צירופי איך אפשר לחשב את הpropagation delay אם לא מחשבים את הדילאיי לכל מסלול במעגל?
translation to English:
How can one compute the longest path in a directed acyclic graph without checking all the paths?
1 Like
This is an important point.
A DAG over n vertices may have a huge number of paths (say, 2^{n/2}).
Clearly, one cannot check all such paths if n=200 (mind you, n=200 is a rather small DAG!).
The algorithm we presented, in fact, runs in linear time (if the fanin is bounded by a constant, then it runs in O(n) time).
This is explained in detail in Chapter 4 (longest path lengths). The case of propagation delays (in which we count the sum of the t_{pd} of gates along paths) is discussed in Chapter 11.