We consider a problem of assigning delays to components in a circuit so that each component is part of a critical path, but the number of edges belonging to critical paths is minimized. We show the problem to be NP-complete via a reduction from finding independent dominating sets in bipartite graphs minimizing dominated edges, and give experimental results on heuristics.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.