mycoreobjectrosdok_document_0000028033rosdok_document_0000028033rosdokdocumentrosdok_derivate_00002299332026-10-20T15:20:07.904Z2026-10-20T15:04:49.785ZMCRJANITOReditorKEpublished1rosdok_derivate_0000229933truetruederivate_types:fulltextVolltextfulltextwf_edit_epub wf_register_epubstate:publishedstate:publishedveröffentlichtpublishedrosdok_id000058951987204301Oau2026-10-202026-10-20T15:19:52ZrdaConverted from PICA to MODS using Pica2MODS XSLT Transformer 2.14-SNAPSHOT [SCM: "" "" ""] with mode 'DEFAULT'.WorkingpaperOptimization of dual-threshold circuitsIn 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.KonradEngel1956 -VerfasserInaut138612366ThomasKalinowski1980 -VerfasserInaut1284202510000-0002-8444-6848RogerLabahn1959 -VerfasserInaut1709996450000-0003-1901-9644FrankSillVerfasserInautDirkTimmermann1957 -VerfasserInaut1327905050000-0001-9267-9695https://purl.uni-rostock.de/rosdok/id00005895urn:nbn:de:gbv:28-rosdok_id00005895-310.18453/rosdok_id00005895510 MathematikMathematisch-Naturwissenschaftliche Fakultätalle Rechte vorbehaltenRechteinhaber Universität Rostockfrei zugänglich (Open Access)Lizenz Metadaten: CC0en1 Online-Ressource (19 Seiten)2005University of Rostock, Institute of MathematicsRostockmonographic20052026Universitätsbibliothek RostockRostock2026Universitätsbibliothek Rostockhttps://purl.uni-rostock.de/rosdok/id00005895Konrad Engel, Thomas Kalinowski, Roger Labahn, Frank Sill, Dirk Timmermannrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/50005-0005doctype:epubdoctype:epubDokumenttypDocument typedoctype:epub.workingpaperdoctype:epub.workingpaperWorkingpaperworking paperdiniPublType:workingPaper diniPublType2022:WorkingPaperinfo:eu-repo/semantics/workingPaperdocumentdiniPublType2022:WorkingPaperdiniPublType2022:WorkingPaperArbeitspapierWorking paperKDSF (Pu37)SDNB:510SDNB:510510 Mathematik510 Mathematicsinstitution:unirostockinstitution:unirostockUniversität RostockUniversity of RostockUniversität RostockUniversität RostockUni.Rostockhttp://d-nb.info/gnd/38329-6institution:unirostock.mnfinstitution:unirostock.mnfMathematisch-Naturwissenschaftliche FakultätFaculty of Mathematics and Natural SciencesUniversität Rostock. Mathematisch-Naturwissenschaftliche FakultätMathematisch-Natur-<br />wissenschaftliche FakultätUni.Rostock.Fakultaet.MNFhttp://d-nb.info/gnd/2147083-2licenseinfo:worklicenseinfo:workWerkworklicenseinfo:work.rightsreservedlicenseinfo:work.rightsreservedalle Rechte vorbehaltenall rights reserved/creativecommons/r/reserved/0.9/88x31.png[DE-28]Urheberrechtsschutz 1.0$gRights Statements$uhttp://rightsstatements.org/vocab/InC/1.0/http://rightsstatements.org/vocab/InC/1.0/http://rightsstatements.org/vocab/InC/1.0/licenseinfo:depositlicenseinfo:depositVeröffentlichungsgenehmigungpermission to storelicenseinfo:deposit.rightsunirostocklicenseinfo:deposit.rightsunirostockRechteinhaber Universität Rostockrightsholder Rostock Universityaccesscondition:openaccessaccesscondition:openaccessfrei zugänglich (Open Access)open accesshttp://purl.org/coar/access_right/c_abf2OAfreeinfo:eu-repo/semantics/openAccess[DE-28]Open Access$gControlled Vocabulary for Access Rights$uhttp://purl.org/coar/access_right/c_abf2licenseinfo:metadatalicenseinfo:metadataLizenzen für Metadatenlicenseinfo:metadata.cc0licenseinfo:metadata.cc0Lizenz Metadaten: CC0license metadata: CC0/creativecommons/p/zero/1.0/88x31.pnghttps://creativecommons.org/publicdomain/zero/1.0/rfc5646:enrfc5646:enEnglischEnglishengengOptimization of dual-threshold circuitsOptimization of dual-threshold circuitsgnd:138612366gnd:128420251orcid:0000-0002-8444-6848gnd:170999645orcid:0000-0003-1901-9644gnd:132790505orcid:0000-0001-9267-9695gnd:138612366gnd:128420251orcid:0000-0002-8444-6848gnd:170999645orcid:0000-0003-1901-9644gnd:132790505orcid:0000-0001-9267-9695rosdok_document_0000028033-d3976943e49gnd:138612366Konrad EngelKonrad Engelrosdok_document_0000028033-d3976943e63gnd:128420251orcid:0000-0002-8444-6848Thomas KalinowskiThomas Kalinowskirosdok_document_0000028033-d3976943e79gnd:170999645orcid:0000-0003-1901-9644Roger LabahnRoger Labahnrosdok_document_0000028033-d3976943e95Frank SillFrank Sillrosdok_document_0000028033-d3976943e105gnd:132790505orcid:0000-0001-9267-9695Dirk TimmermannDirk TimmermannKonrad EngelThomas KalinowskiRoger LabahnFrank SillDirk TimmermannKonrad EngelThomas KalinowskiRoger LabahnFrank SillDirk TimmermannKonrad EngelThomas KalinowskiRoger LabahnFrank SillDirk TimmermannRostockUniversity of Rostock, Institute of Mathematicsepub.workingpaperhttps://purl.uni-rostock.de/rosdok/id00005895urn:nbn:de:gbv:28-rosdok_id00005895-310.18453/rosdok_id00005895In 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.20052005Preprints aus dem Institut für Mathematikrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/50005-0005https://purl.uni-rostock.de/rosdok/id000058163255797-8Konrad Engel, Thomas Kalinowski, Roger Labahn, Frank Sill, Dirk Timmermannepub.workingpaper1 Engel_optimization_2005.pdf 184617 6c9960b004d683aa27d4038194cd3e25 rosdok_id000058951987204301Oau2026-10-202026-10-20T15:19:52ZrdaConverted from PICA to MODS using Pica2MODS XSLT Transformer 2.14-SNAPSHOT [SCM: "" "" ""] with mode 'DEFAULT'.WorkingpaperOptimization of dual-threshold circuitsIn 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.KonradEngel1956 -VerfasserInaut138612366ThomasKalinowski1980 -VerfasserInaut1284202510000-0002-8444-6848RogerLabahn1959 -VerfasserInaut1709996450000-0003-1901-9644FrankSillVerfasserInautDirkTimmermann1957 -VerfasserInaut1327905050000-0001-9267-9695https://purl.uni-rostock.de/rosdok/id00005895urn:nbn:de:gbv:28-rosdok_id00005895-310.18453/rosdok_id00005895510 MathematikMathematisch-Naturwissenschaftliche Fakultätalle Rechte vorbehaltenRechteinhaber Universität Rostockfrei zugänglich (Open Access)Lizenz Metadaten: CC0en1 Online-Ressource (19 Seiten)2005University of Rostock, Institute of MathematicsRostockmonographic20052026Universitätsbibliothek RostockRostock2026Universitätsbibliothek Rostockhttps://purl.uni-rostock.de/rosdok/id00005895Konrad Engel, Thomas Kalinowski, Roger Labahn, Frank Sill, Dirk Timmermannrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/50005-0005 2026-10-20T15:04:49.785Z 2026-10-20T15:20:07.904Z 2026-10-30T15:20:07.916Z editorKE {"identifier":"rosdok/id00005895","type":"local_id","additional":"","service":"MCRLocalID","created":"2026-10-20T15:04:49.792Z"} {"identifier":"urn:nbn:de:gbv:28-rosdok_id00005895-3","type":"dnbUrn","additional":"","service":"RosDokURN","created":"2026-10-20T15:04:49.799Z"} {"identifier":"https://purl.uni-rostock.de/rosdok/id00005895","type":"purl","additional":"","service":"RosDokPURL","created":"2026-10-20T15:04:49.803Z","registrationStarted":"2026-10-20T15:20:06.712Z"} {"identifier":"10.18453/rosdok_id00005895","type":"doi","additional":"","service":"RosDokDOI","created":"2026-10-20T15:04:49.807Z","registrationStarted":"2026-10-20T15:20:06.464Z","registered":"2026-10-20T15:20:07.902Z"} MCRJANITORfulltextfile/rosdok_document_0000028033/rosdok_derivate_0000229933/Engel_optimization_2005.pdfOptimization of dual-threshold circuitsOptimization of dual-threshold circuitsgnd:138612366gnd:128420251orcid:0000-0002-8444-6848gnd:170999645orcid:0000-0003-1901-9644gnd:132790505orcid:0000-0001-9267-9695gnd:138612366gnd:128420251orcid:0000-0002-8444-6848gnd:170999645orcid:0000-0003-1901-9644gnd:132790505orcid:0000-0001-9267-9695rosdok_document_0000028033-d3976943e49gnd:138612366Konrad EngelKonrad Engelrosdok_document_0000028033-d3976943e63gnd:128420251orcid:0000-0002-8444-6848Thomas KalinowskiThomas Kalinowskirosdok_document_0000028033-d3976943e79gnd:170999645orcid:0000-0003-1901-9644Roger LabahnRoger Labahnrosdok_document_0000028033-d3976943e95Frank SillFrank Sillrosdok_document_0000028033-d3976943e105gnd:132790505orcid:0000-0001-9267-9695Dirk TimmermannDirk TimmermannKonrad EngelThomas KalinowskiRoger LabahnFrank SillDirk TimmermannKonrad EngelThomas KalinowskiRoger LabahnFrank SillDirk TimmermannKonrad EngelThomas KalinowskiRoger LabahnFrank SillDirk TimmermannRostockUniversity of Rostock, Institute of Mathematicsepub.workingpaperhttps://purl.uni-rostock.de/rosdok/id00005895urn:nbn:de:gbv:28-rosdok_id00005895-310.18453/rosdok_id00005895In 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.20052005Preprints aus dem Institut für Mathematikrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/50005-0005https://purl.uni-rostock.de/rosdok/id000058163255797-8Konrad Engel, Thomas Kalinowski, Roger Labahn, Frank Sill, Dirk Timmermann[xslt]Saxonrosdok_id00005895https://purl.uni-rostock.de/rosdok/id00005895198720430110.18453/rosdok_id00005895urn:nbn:de:gbv:28-rosdok_id00005895-3Konrad Engel, Thomas Kalinowski, Roger Labahn, Frank Sill, Dirk TimmermannEngel Konrad, Kalinowski Thomas, Labahn Roger, Sill Frank, Timmermann DirkOptimization of dual-threshold circuitsWorkingpaperworking paperUniversity of Rostock, Institute of Mathematics, 2005In 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…rosdok_id000058160005-000505/5Konrad EngelThomas KalinowskiRoger LabahnFrank SillDirk TimmermannOptimization of dual-threshold circuitsPreprints aus dem Institut für MathematikUniversitätsbibliothek Rostockhttps://purl.uni-rostock.de/rosdok/id00005895KonradEngel1956 -VerfasserInaut138612366ThomasKalinowski1980 -VerfasserInaut1284202510000-0002-8444-6848RogerLabahn1959 -VerfasserInaut1709996450000-0003-1901-9644FrankSillVerfasserInautDirkTimmermann1957 -VerfasserInaut1327905050000-0001-9267-9695[purl]https://purl.uni-rostock.de/rosdok/id00005895[urn]urn:nbn:de:gbv:28-rosdok_id00005895-3[doi]10.18453/rosdok_id00005895open_access20052005epoch:21th_centuryrfc5646:endoctype:epub.workingpaperaccesscondition:openaccessSDNB:510institution:unirostock.mnfstate:published