Graph-driven free parity BDDs: Algorithms and lower bounds
2001 | conference paper. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Cite this publication
Brosenne H, Homeister M, Waack S. Graph-driven free parity BDDs: Algorithms and lower bounds. In: Sgall J, editor. Mathematical foundations of computer science 2001. 26th International Symposium on Mathematical Foundations of Computer Science; 2001-08-27 - 2001-08-31; Mariánské Lázně, Czech Republic. Berlin: Springer; 2001. p. 212-223. (Lecture Notes in Computer Science; vol. 2136).
Documents & Media
Details
- Authors
- Brosenne, H. ; Homeister, M.; Waack, S.
- Editors
- Sgall, Jiří
- Abstract
- We investigate graph-driven free paxity BDDs, which strictly generalize the two well-known models parity OBDDs and graph-driven free BDDs. The first main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven free parity BDD. The second main result is an exponential lower bound on the size of graph-driven free parity BDD for linear code functions.
- Issue Date
- 2001
- Publisher
- Springer
- Conference
- 26th International Symposium on Mathematical Foundations of Computer Science
- Series
- Lecture Notes in Computer Science
- ISBN
- 3-540-42496-2
- Conference Place
- Mariánské Lázně, Czech Republic
- Event start
- 2001-08-27
- Event end
- 2001-08-31
- ISSN
- 0302-9743
- Language
- English
