David Eppstein – Publications

Publications with L. Singhal, Love Singhal

• Interconnect criticality driven delay relaxation.
  L. Singhal, E. Bozorgzadeh, and D. Eppstein.
  IEEE Trans. CAD 26 (10): 1803–1817, 2007.

  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.