This article is cited in 1 scientific paper (total in 1 paper)
Proof of covering minimality by generalizing the notion of independence
I. P. Chukhrov
Institute of Computer Aided Design RAS, 19/18 Vtoraya Brestskaya St., 123056 Moscow, Russia
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.
set covering problem, complexity, shortest cover, minimum cover, independent set, lower bound, condition of minimality.
PDF file (347 kB)
Journal of Applied and Industrial Mathematics, 2017, 11:2, 193–203
I. P. Chukhrov, “Proof of covering minimality by generalizing the notion of independence”, Diskretn. Anal. Issled. Oper., 24:2 (2017), 87–106; J. Appl. Industr. Math., 11:2 (2017), 193–203
Citation in format AMSBIB
\paper Proof of covering minimality by generalizing the notion of independence
\jour Diskretn. Anal. Issled. Oper.
\jour J. Appl. Industr. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
I. P. Chukhrov, “On the complexity of minimizing quasicyclic Boolean functions”, J. Appl. Industr. Math., 12:3 (2018), 426–441
|Number of views:|