Sign in
Back
On algorithms for construction of all irreducible partial covers
Journal article   Peer reviewed

On algorithms for construction of all irreducible partial covers

Mikhail Ju Moshkov
Information processing letters, Vol.103(2), pp.66-70
16/07/2007
DOI: https://doi.org/10.1016/j.ipl.2007.02.009

Abstract

Computational complexity Irreducible partial cover Totally polynomial algorithm
Lower and upper bounds on the cardinality and the number of irreducible partial covers for almost all set cover problems are obtained. These bounds allow us to prove that there is no polynomial algorithm which for almost all set cover problems constructs all irreducible partial covers, but there exists a totally polynomial algorithm which constructs all irreducible partial covers for almost all set cover problems.

Metrics

1 Record Views

Details