Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2012
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1208.2559 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.