2012/08/13 by Wild, Marcel
#68Q25 #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1208.2559
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.