Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2012
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/1208.2559 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908302934278144 |
|---|---|
| author | Wild, Marcel |
| author_facet | Wild, Marcel |
| contents | Let $W$ be a finite set which simultaneously serves as the universe of any poset $(W,\preceq)$ and as the vertex set of any graph $G$. Our algorithm, abbreviated A-I-I, enumerates (in a compressed format using don't-care symbols) all $G$-independent order ideals of $(W,\preceq)$. For many instances the high-end Mathematica implementation of A-I-I compares favorably to the hardwired Mathematica commands {\tt BooleanConvert} and {\tt SatisfiabilityCount}. The A-I-I can be parallelized and adapts to a polynomial total time algorithm that enumerates the modelset of any Boolean 2-CNF. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1208_2559 |
| institution | arXiv |
| publishDate | 2012 |
| record_format | arxiv |
| spellingShingle | Compression with wildcards: All models of a Boolean 2-CNF Wild, Marcel Computational Complexity 68Q25 Let $W$ be a finite set which simultaneously serves as the universe of any poset $(W,\preceq)$ and as the vertex set of any graph $G$. Our algorithm, abbreviated A-I-I, enumerates (in a compressed format using don't-care symbols) all $G$-independent order ideals of $(W,\preceq)$. For many instances the high-end Mathematica implementation of A-I-I compares favorably to the hardwired Mathematica commands {\tt BooleanConvert} and {\tt SatisfiabilityCount}. The A-I-I can be parallelized and adapts to a polynomial total time algorithm that enumerates the modelset of any Boolean 2-CNF. |
| title | Compression with wildcards: All models of a Boolean 2-CNF |
| topic | Computational Complexity 68Q25 |
| url | https://arxiv.org/abs/1208.2559 |