Geodesic
Proof of covering minimality by generalizing the notion of independence
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 87-106

Voir la notice de l'article provenant de la source Math-Net.Ru

A method is proposed for obtaining lower bounds for the length of the shortest cover and complexity of the minimal cover based on the notion of independent family of sets. For the problem of minimization of Boolean functions, we provide the functions and construct coverings by faces of the set of unit vertices for which the suggested lower bounds can be achieved in the case of five or more variables. The lower bounds, based on independent sets, are unreachable and cannot be used as sufficient conditions for minimality of such functions. Bibliogr. 11.
Keywords: set covering problem, complexity, shortest cover, minimum cover, independent set, lower bound, condition of minimality. 
@article{DA_2017_24_2_a5,
     author = {I. P. Chukhrov},
     title = {Proof of covering minimality by generalizing the notion of independence},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {87--106},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_2_a5/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - Proof of covering minimality by generalizing the notion of independence
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 87
EP  - 106
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_2_a5/
LA  - ru
ID  - DA_2017_24_2_a5
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T Proof of covering minimality by generalizing the notion of independence
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 87-106
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_2_a5/
%G ru
%F DA_2017_24_2_a5
I. P. Chukhrov. Proof of covering minimality by generalizing the notion of independence. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 87-106. http://geodesic.mathdoc.fr/item/DA_2017_24_2_a5/