10.18453/rosdok_id00005895 Engel, Konrad Konrad Engel http://d-nb.info/gnd/138612366 Kalinowski, Thomas Thomas Kalinowski http://d-nb.info/gnd/128420251 https://orcid.org/0000-0002-8444-6848 Labahn, Roger Roger Labahn http://d-nb.info/gnd/170999645 https://orcid.org/0000-0003-1901-9644 Sill, Frank Frank Sill Timmermann, Dirk Dirk Timmermann http://d-nb.info/gnd/132790505 https://orcid.org/0000-0001-9267-9695 University of Rostock, Institute of Mathematics 2005 510 Mathematics 2005 en https://purl.uni-rostock.de/rosdok/id00005895 urn:nbn:de:gbv:28-rosdok_id00005895-3 In this paper, we consider an optimization problem on directed acyclic graphs which is motivated by a standard task in low power VLSI design. With each vertex v of a directed acyclic graph, we associate two delay values d0(v) ≤ d1(v) and two leakage values c0(v) ≥ c1(v). The objective is to choose one of the indices 0 or 1 for each vertex, such that in first instance the corresponding total delay along any directed path is minimal, and in second instance the total leakage is minimized. We prove that a very restricted special case of this problem already is NP-hard, and we present four different heuristic approaches to the problem. Further, we test our algorithms on ISCAS85 benchmark circuits.