On algorithms for construction of all irreducible partial covers

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)66-70
Number of pages5
JournalInformation Processing Letters
Volume103
Issue number2
DOIs
StatePublished - Jul 16 2007

Keywords

  • Computational complexity
  • Irreducible partial cover
  • Totally polynomial algorithm

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On algorithms for construction of all irreducible partial covers'. Together they form a unique fingerprint.

Cite this