2017/08/05 by Mikolas Janota, Radu Grigore, Janota, Mikolas +3
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.LO
paper · pdf · doi:10.48550/arxiv.1708.01745
RCRA2017
arxiv created 2017/10/09 · arxiv updated 2017/10/10
The paper aims at finding acyclic graphs under a given set of constraints. More specifically, given a propositional formula ϕ over edges of a fixed-size graph, the objective is to find a model of ϕ that corresponds to a graph that is acyclic. The paper proposes several encodings of the problem and compares them in an experimental evaluation using stateof-the-art SAT solvers.