Due to the statistical nature of gate delays in current day technologies, measures such as path criticality and node/edge criticality are required for timing optimization. Node criticalities are usually computed using the complementary path delay. In order to speed up computations, it has been recently proposed that the circuit delay be used instead. In this paper, we show that there is a monotonic relationship between the node criticalities computed using the circuit delay and the complementary delay. They are not equal, but they can be used interchangeably. We discuss the sources of error in this computation and propose methods for more accurate computations. We also introduce a measure that is very easy to compute and is an approximate indicator of criticality. Since it is easy to compute, it can also be used effectively for pruning the number of edges involved in criticality computations thus improving the speed of criticality computations. The speedup obtained can be as large as an order of magnitude for some of larger circuits in the ISCAS benchmarks. © 2012 ACM.