Dijkstra Constructions for Improved Performance-

tree delay, average tree delay (i.e., sum of delays to all the pins), or any other well-behaved delay function. Because the typical CAD environment consists of a large network of workstations and servers, there is tremendous potential for improvement of running times through parallel/distributed implementations [2] [5]. We note that algorithms described in this paper are highly parallelizable, e.g. the BBORT method can use p processors to simultaneously explore routing topologies in di erent regions of the solution space. Similarly, the LDT algorithm can employ separate processors to determine the e ects on delay of adding di erent candidate edges to the growing routing topology.