Finding small OBDDs for incompletely specified truth tables is hard

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
We present an efficient reduction mapping undirected graphs
G with n = 2^k vertices for integers k to tables of partially
specified Boolean functions g: {0,1}^(4k+1) -> {0,1,*}
so that for any integer m, G has a vertex colouring
using m colours if and only if g has a consistent ordered binary
decision diagram with at most (2m + 2)n^2 + 4n decision nodes.
From this it follows that the problem of finding a minimum-sized
consistent OBDD for an incompletely specified truth table is
NP-hard and also hard to approximate.
Original languageEnglish
Title of host publicationComputing and Combinatorics : 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006. Proceedings
EditorsDanny Z. Chen, D. T. Lee
Number of pages8
PublisherSpringer
Publication year2006
Pages489-496
DOIs
Publication statusPublished - 2006
EventAnnual International Conference on Computing and Combinatorics. COCOON 2006 - Taipei, Taiwan
Duration: 15 Aug 200618 Aug 2006
Conference number: 12

Conference

ConferenceAnnual International Conference on Computing and Combinatorics. COCOON 2006
Nummer12
LandTaiwan
ByTaipei
Periode15/08/200618/08/2006
SeriesLecture Notes in Computer Science
Volume4112
ISSN0302-9743

    Research areas

  • OBDDs, partial boolean functions

See relations at Aarhus University Citationformats

ID: 3688736