Paper Info
Title
Strong Duality in Horn Minimization.
Abstract
A pure Horn CNF is minimal if no shorter pure Horn CNF representing the same function exists, where the CNF length may mean several different things, e.g. the number of clauses, or the total number of literals (sum of clause lengths), or the number of distinct bodies (source sets). The corresponding minimization problems (a different problem for each measure of the CNF size) appear not only in the Boolean context, but also as problems on directed hypergraphs or problems on closure systems. While minimizing the number of clauses or the total number of literals is computationally very hard, minimizing the number of distinct bodies is polynomial time solvable. There are several algorithms in the literature solving this task.
Year
Venue
Field
2017
FCT
Discrete mathematics,Combinatorics,Duality gap,Constraint graph,Minification,Duality (optimization),Strong duality,Time complexity,Convex analysis,Mathematics
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
11
3
Name
Order
Citations
PageRank
Endre Boros11779155.63
Ondrej Cepek2559.40
Kazuhisa Makino31088102.74