Department of Computer Science & Engineering

Routing zero skew clock tree with minimum cost is formulated as Path-length Balanced Tree (PBT) problem. Various heuristics have been proposed. The nature of the problem is still open. We prove that PBT problem is NP-complete in Manhattan, Euclidean, and diagonal planes, and present an approximation scheme for path-length delay model with $N^{1+clgN}$ to achieve (1+1/c) OPTIMUM.

Pre-2018 CSE ID: CS2005-0837