במעגל צירופי איך אפשר לחשב את הpropagation delay אם לא מחשבים את הדילאיי לכל מסלול במעגל?

translation to English:

How can one compute the longest path in a directed acyclic graph without checking all the paths?

במעגל צירופי איך אפשר לחשב את ה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.