Geodesic
Design and research of the parallel combinatorial algorithms
Prikladnaâ diskretnaâ matematika, no. 2 (2009), pp. 96-103 
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/
@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},
     year = {2009},
     number = {2},
     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
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
%U http://geodesic.mathdoc.fr/item/PDM_2009_2_a6/
%G ru
%F PDM_2009_2_a6

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.

[1] Timoshevskaya N. E., “O metodakh razrabotki parallelnykh kombinatornykh algoritmov”, Tretya Sibirskaya shkola-seminar po parallelnym vychisleniyam, eds. A. V. Starchenko, Izd-vo Tom. un-ta, Tomsk, 2006, 60–72

[2] Timoshevskaya N. E., “Parallelnye metody obkhoda dereva”, Matematicheskoe modelirovanie., 16:1 (2004), 105–114 | MR | Zbl

[3] Belyaev V. A., Timoshevskaya N. E., “Rasparallelivanie obkhoda dereva poiska dlya resheniya zadachi o ryukzake na klasternoi sisteme”, Vysokoproizvoditelnye parallelnye vychisleniya na klasternykh sistemakh, Materialy Mezhdunar. nauch.-praktich. sem., eds. prof. R. G. Strongin, Izd-vo Nizhegor. un-ta, N. Novgorod, 2002, 16–20

[4] Timoshevskaya N. E., “O numeratsii perestanovok i sochetanii dlya organizatsii parallelnykh vychislenii v zadachakh proektirovaniya upravlyayuschikh sistem”, Izv. Tomskogo politekhnicheskogo universiteta, 307:6 (2004), 18–20

[5] Timoshevskaya N. E., “Parallelnoe perechislenie razbienii mnozhestva metodom numeratsii”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2006, no. 17, 260–264

[6] Timoshevskaya N. E., “Zadacha o kratchaishem linearizatsionnom mnozhestve”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2005, no. 4, 79–83

[7] Timoshevskaya N. E., “O linearizatsionno ekvivalentnykh pokrytiyakh”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2005, no. 4, 84–91

[8] Timoshevskaya N. E., “Parallelnye vychisleniya v reshenii sistem logicheskikh uravnenii metodom linearizatsii”, Materialy KhV Mezhdunar. shkoly-seminara “Sintez i slozhnost upravlyayuschikh sistem” (Novosibirsk, 18–23 oktyabrya 2004 g.), Institut matematiki, Novosibirsk, 2004, 97–102