DESIGN AND RESEARCH OF THE PARALLEL COMBINATORIAL ALGORITHMS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2009. № 2(4).

The design of effective parallel combinatorial algorithms is an actual problem for the modern discrete mathematics. Here we inform about the results in this area. Two parallel methods for making tree search on a cluster computing system are proposed. Also, some results concerning the linearization-set method for solving the system of nonlinear logical equations are given. The problem under consideration is determining the shortest linearization subset for a given set cover. NP-hardness of the problem is proved. The connection with the minimum vertex cover problem is shown. Thedefinition of linearization-equivalent coverings is entered and an effective method for equivalence checking with the help of graphs is given. The minimal, shortest and irredundant coverings in the equivalent class are defined and some their properties are researched. We have proved that the problem of finding the shortest equivalent cover is NP-hard and we propose an approximate algorithm for its solution.