Abstract
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.
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.
| Originalsprog | Engelsk |
|---|---|
| Titel | Computing and Combinatorics : 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006. Proceedings |
| Redaktører | Danny Z. Chen, D. T. Lee |
| Antal sider | 8 |
| Forlag | Springer |
| Publikationsdato | 2006 |
| Sider | 489-496 |
| DOI | |
| Status | Udgivet - 2006 |
| Begivenhed | Annual International Conference on Computing and Combinatorics. COCOON 2006 - Taipei, Taiwan Varighed: 15 aug. 2006 → 18 aug. 2006 Konferencens nummer: 12 |
Konference
| Konference | Annual International Conference on Computing and Combinatorics. COCOON 2006 |
|---|---|
| Nummer | 12 |
| Land/Område | Taiwan |
| By | Taipei |
| Periode | 15/08/2006 → 18/08/2006 |
| Navn | Lecture Notes in Computer Science |
|---|---|
| Vol/bind | 4112 |
| ISSN | 0302-9743 |