Informace o publikaci
Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theory of Computing Systems |
| Citace | |
| Doi | http://dx.doi.org/10.1007/s00224-007-9067-9 |
| Klíčová slova | Binary decision diagrams; Free binary decision diagrams |
| Popis | A binary decision diagram (BDD) is a graph-based data structure representing Boolean functions; a""-BDDs are BDDs with an additional restriction that each input bit can be tested at most a"" times. A d-uniform hypergraph H on N vertices is an exactly half-d-hyperclique if N/2 of its vertices form a hyperclique and the remaining vertices are isolated. Wegener [J. ACM 35(2), 461-471 (1988)] conjectured that there is no polynomial-size (d-1)-BDD for the Exactly half-d-hyperclique problem. We refute this conjecture by constructing polynomial-size (syntactic) 2-BDDs for the Exactly half-d-hyperclique problem for every da parts per thousand yen2. |