Publication details
Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Periodical |
| Magazine / Source | Theory of Computing Systems |
| Citation | |
| Doi | http://dx.doi.org/10.1007/s00224-007-9067-9 |
| Keywords | Binary decision diagrams; Free binary decision diagrams |
| Description | 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. |