On algorithms for construction of all irreducible partial covers

Mikhail Moshkov

doi:10.1016/j.ipl.2007.02.009

On algorithms for construction of all irreducible partial covers

Mikhail Moshkov^*

^*Corresponding author for this work

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	66-70
Number of pages	5
Journal	Information Processing Letters
Volume	103
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2007.02.009
State	Published - Jul 16 2007

Keywords

Computational complexity
Irreducible partial cover
Totally polynomial algorithm

ASJC Scopus subject areas

Computational Theory and Mathematics

Access to Document

10.1016/j.ipl.2007.02.009

Cite this

@article{e8f75dfad0c0422cabc60185f7d0ef7d,

title = "On algorithms for construction of all irreducible partial covers",

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.",

keywords = "Computational complexity, Irreducible partial cover, Totally polynomial algorithm",

author = "Mikhail Moshkov",

year = "2007",

month = jul,

day = "16",

doi = "10.1016/j.ipl.2007.02.009",

language = "English (US)",

volume = "103",

pages = "66--70",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - On algorithms for construction of all irreducible partial covers

AU - Moshkov, Mikhail

PY - 2007/7/16

Y1 - 2007/7/16

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Irreducible partial cover

KW - Totally polynomial algorithm

UR - http://www.scopus.com/inward/record.url?scp=34247499344&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2007.02.009

DO - 10.1016/j.ipl.2007.02.009

M3 - Article

AN - SCOPUS:34247499344

SN - 0020-0190

VL - 103

SP - 66

EP - 70

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

On algorithms for construction of all irreducible partial covers

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this