On algorithms for construction of all irreducible partial covers

Mikhail Ju Moshkov

doi:10.1016/j.ipl.2007.02.009

On algorithms for construction of all irreducible partial covers

Mikhail Ju Moshkov^*

^*Corresponding author for this work

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
Externally published	Yes

Keywords

Computational complexity
Irreducible partial cover
Totally polynomial algorithm

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Signal Processing
Computer Science Applications

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 = "Moshkov, {Mikhail Ju}",

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 Ju

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