Geodesic
Design and research of the parallel combinatorial algorithms
Prikladnaâ diskretnaâ matematika, no. 2 (2009), pp. 96-103

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

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. The definition 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. 
@article{PDM_2009_2_a6,
     author = {N. E. Timoshevskaya},
     title = {Design and  research of the parallel combinatorial algorithms},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {96--103},
     publisher = {mathdoc},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2009_2_a6/}
}
TY  - JOUR
AU  - N. E. Timoshevskaya
TI  - Design and  research of the parallel combinatorial algorithms
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2009
SP  - 96
EP  - 103
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2009_2_a6/
LA  - ru
ID  - PDM_2009_2_a6
ER  - 
%0 Journal Article
%A N. E. Timoshevskaya
%T Design and  research of the parallel combinatorial algorithms
%J Prikladnaâ diskretnaâ matematika
%D 2009
%P 96-103
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2009_2_a6/
%G ru
%F PDM_2009_2_a6
N. E. Timoshevskaya. Design and  research of the parallel combinatorial algorithms. Prikladnaâ diskretnaâ matematika, no. 2 (2009), pp. 96-103. http://geodesic.mathdoc.fr/item/PDM_2009_2_a6/