On the sizes of BDDs and ZDDs representing matroids
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910418617761792 |
|---|---|
| author | Emoto, Hiromi Iwamasa, Yuni Minato, Shin-ichi |
| author_facet | Emoto, Hiromi Iwamasa, Yuni Minato, Shin-ichi |
| contents | Matroids are often represented as oracles since there are no unified and compact representations for general matroids. This paper initiates the study of binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) as relatively compact data structures for representing matroids in a computer. This study particularly focuses on the sizes of BDDs and ZDDs representing matroids. First, we compare the sizes of different variations of BDDs and ZDDs for a matroid. These comparisons involve concise transformations between specific decision diagrams. Second, we provide upper bounds on the size of BDDs and ZDDs for several classes of matroids. These bounds are closely related to the number of minors of the matroid and depend only on the connectivity function or pathwidth of the matroid, which deeply relates to the classes of matroids called strongly pigeonhole classes. In essence, these results indicate upper bounds on the number of minors for specific classes of matroids and new strongly pigeonhole classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14670 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the sizes of BDDs and ZDDs representing matroids Emoto, Hiromi Iwamasa, Yuni Minato, Shin-ichi Combinatorics Discrete Mathematics Data Structures and Algorithms Matroids are often represented as oracles since there are no unified and compact representations for general matroids. This paper initiates the study of binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) as relatively compact data structures for representing matroids in a computer. This study particularly focuses on the sizes of BDDs and ZDDs representing matroids. First, we compare the sizes of different variations of BDDs and ZDDs for a matroid. These comparisons involve concise transformations between specific decision diagrams. Second, we provide upper bounds on the size of BDDs and ZDDs for several classes of matroids. These bounds are closely related to the number of minors of the matroid and depend only on the connectivity function or pathwidth of the matroid, which deeply relates to the classes of matroids called strongly pigeonhole classes. In essence, these results indicate upper bounds on the number of minors for specific classes of matroids and new strongly pigeonhole classes. |
| title | On the sizes of BDDs and ZDDs representing matroids |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.14670 |