33 citations · 81 across the 32 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2012
Hardness Results for Approximate Pure Horn CNF Formulae Minimization
Endre Boros, Aritanan Gruber
We study the hardness of approximation of clause minimum and literal minimum representations of pure Horn functions in Boolean variables. We show that unless P=NP, it is not po…
cs.CC2008
Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra
Endre Boros, Khaled Elbassioni, Vladimir Gurvich +1
Given a graph and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron of negative-weight flows on , and get a complete characterization…