Sample Method for Minimization of OBDDs
Identifieur interne : 000E85 ( Istex/Curation ); précédent : 000E84; suivant : 000E86Sample Method for Minimization of OBDDs
Auteurs : Anna Slobodova [États-Unis, Slovaquie] ; Christoph Meinel [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1998.
Abstract
Abstract: The exact minimization of the size of Ordered Binary Decision Diagrams (OBDD) is known to be an NP-complete problem. The available heuristical solutions of the problem still do not satisfy requirements of the practical applications. Development of the efficient algorithms that find acceptable variable orders within a short time and with a modest memory overhead is hence higly desired. In this paper we contribute to the solution of the minimization problem by a new variable reordering heuristic that is based on sampling. A small OBDD sample is chosen from the OBDDs that are considered for minimization. Solving the problem for this small sample, we obtain a variable order that is extrapolated and applied to the entire OBDDs. We present the first experimental results with the Sample Reordering targeted at combinatorial verification. The suggested heuristic is substantially faster than Sifting.
Url:
DOI: 10.1007/3-540-49477-4_34
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000F95
Links to Exploration step
ISTEX:44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Sample Method for Minimization of OBDDs</title><author><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodova">Anna Slobodova</name><affiliation wicri:level="1"><mods:affiliation>Compaq, Shrewsbury, Massachusets, USA</mods:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Compaq, Shrewsbury, Massachusets</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>Comenius University, Bratislava, Slovakia</mods:affiliation><country xml:lang="fr">Slovaquie</country><wicri:regionArea>Comenius University, Bratislava</wicri:regionArea></affiliation><affiliation><mods:affiliation>E-mail: slobodov@cadunx.hlo.dec.com</mods:affiliation><wicri:noCountry code="no comma">E-mail: slobodov@cadunx.hlo.dec.com</wicri:noCountry></affiliation></author><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><mods:affiliation>Institute of Telematics, Bahnhofstr 30-32, 54292, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institute of Telematics, Bahnhofstr 30-32, 54292, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>FB IV - Informatik, University of Trier, 54286, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV - Informatik, University of Trier, 54286, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: meinel@ti.fhg.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1007/3-540-49477-4_34</idno><idno type="url">https://api.istex.fr/document/44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000F95</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000F95</idno><idno type="wicri:Area/Istex/Curation">000E85</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Sample Method for Minimization of OBDDs</title><author><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodova">Anna Slobodova</name><affiliation wicri:level="1"><mods:affiliation>Compaq, Shrewsbury, Massachusets, USA</mods:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Compaq, Shrewsbury, Massachusets</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>Comenius University, Bratislava, Slovakia</mods:affiliation><country xml:lang="fr">Slovaquie</country><wicri:regionArea>Comenius University, Bratislava</wicri:regionArea></affiliation><affiliation><mods:affiliation>E-mail: slobodov@cadunx.hlo.dec.com</mods:affiliation></affiliation></author><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><mods:affiliation>Institute of Telematics, Bahnhofstr 30-32, 54292, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institute of Telematics, Bahnhofstr 30-32, 54292, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>FB IV - Informatik, University of Trier, 54286, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV - Informatik, University of Trier, 54286, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: meinel@ti.fhg.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1998</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8</idno><idno type="DOI">10.1007/3-540-49477-4_34</idno><idno type="ChapterID">34</idno><idno type="ChapterID">Chap34</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The exact minimization of the size of Ordered Binary Decision Diagrams (OBDD) is known to be an NP-complete problem. The available heuristical solutions of the problem still do not satisfy requirements of the practical applications. Development of the efficient algorithms that find acceptable variable orders within a short time and with a modest memory overhead is hence higly desired. In this paper we contribute to the solution of the minimization problem by a new variable reordering heuristic that is based on sampling. A small OBDD sample is chosen from the OBDDs that are considered for minimization. Solving the problem for this small sample, we obtain a variable order that is extrapolated and applied to the entire OBDDs. We present the first experimental results with the Sample Reordering targeted at combinatorial verification. The suggested heuristic is substantially faster than Sifting.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000E85 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 000E85 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8
|texte= Sample Method for Minimization of OBDDs
}}
| This area was generated with Dilib version V0.6.31. |  |