Ananiashvili, Natela Solution of problems of minimal set partition and set covering. (English) Zbl 1339.90271 Bull. Georgian Natl. Acad. Sci. (N.S.) 9, No. 1, 38-43 (2015). Summary: The article considers solution of minimal set partition and set covering problems. As is known, the problems of minimal set partition and set covering belong to the class of complex NP problems. The efficient algorithm for precise solution of such problems does not exist nowadays (except in private cases). Solution time depends on a scale of the problem and it may significantly increase with it. A tree algorithm of simplified search is used. It became possible to decrease volume of occupied memory approximately 32\(\cdot\)M-times with non-essential elaboration of programming techniques and computational time decreased approximately 32\(\cdot\)M-times, where M is a number of covering subsets. For this purpose, partition matrix was compactly written and then basic operations were performed on columns of the matrix with logical operators. A complex of programs was developed in algorithmic language C++ and realized in Dev-C++ environment to solve these problems and check them on tests taken from ORLibrary and real combinative problems that are known from the literature. The results are satisfactory and given in reasonable amount of time. The proposed complex of programs may be used for solution of the other problems of graph theory that can be deduced to problems of minimal set partition or set covering, or they are the sub-problems of such problems (for instance, problem of searching of dominant set of graph nodes). MSC: 90C27 Combinatorial optimization Keywords:set covering; set partition; precise solution Software:OR-Library PDFBibTeX XMLCite \textit{N. Ananiashvili}, Bull. Georgian Natl. Acad. Sci. (N.S.) 9, No. 1, 38--43 (2015; Zbl 1339.90271) Full Text: Link