Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice

KRÁĽ, Daniel. Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice. Theory of Computing Systems. New York: Springer, 2009, roč. 45, č. 1, s. 27-42. ISSN 1432-4350. Dostupné z: https://doi.org/10.1007/s00224-007-9067-9.

Základní údaje

Originální název

Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice

Autoři

KRÁĽ, Daniel

Vydání

Theory of Computing Systems, New York, Springer, 2009, 1432-4350

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.726

DOI

https://doi.org/10.1007/s00224-007-9067-9

UT WoS

000265566300002

Klíčová slova anglicky

Binary decision diagrams; Free binary decision diagrams

---

Anotace

V originále

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.