ABSTRACT
A combinational logic circuit may be represented as a timing graph G = (V, E), where the elements of V, the vertex set, are the inputs and outputs of the logic gates in the circuit. e vertices are connected by two types of edges: one set of edges connects each input of a gate to its output, which represents the maximum delay paths from the input pin to the output pin, while another set of edges connects the output of each gate to the inputs of its fanout gates and corresponds to the interconnect delays. A simple logic circuit and its corresponding graph are illustrated in Figure 6.1a and b, respectively. We refer to fanin-free nodes as primary inputs and nodes whose values are observed (which may or may not be fanout free) as primary outputs.
