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
Graph-driven free parity BDDs: Algorithms and lower bounds
Brosenne, H. ; Homeister, M. & Waack, S. (2001)
In:Sgall, Jiří (Ed.), Mathematical foundations of computer science 2001 pp. 212-223. 26th International Symposium on Mathematical Foundations of Computer Science, Mariánské Lázně, Czech Republic.
Berlin: Springer.
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