Loading…
Academic Journal
Parallel calculations by automata on direct and back spanning trees of a graph
Igor Burdonov, Alexander Kossachev, Victor Kuliamin
Труды Института системного программирования РАН, Vol 26, Iss 6, Pp 63-66 (2018)
Saved in:
| Title | Parallel calculations by automata on direct and back spanning trees of a graph |
|---|---|
| Authors | Igor Burdonov, Alexander Kossachev, Victor Kuliamin |
| Publication Year |
2018
|
| Source |
Труды Института системного программирования РАН, Vol 26, Iss 6, Pp 63-66 (2018)
|
| Description |
The paper presents a parallel computation algorithm of an arbitrary function value on a multiset of values distributed on directed graph vertices. The computation is performed by message passing executed by automata distributed on the graph vertices. The key idea of the algorithm is to use a structural information on the graph that can be extracted by its parallel exploration and encoded into structures of direct and back spanning trees of the graph, which require only finite number of bits in each graph vertex, and to represent the function calculated as a composition of so called aggregate function and another one. Aggregate functions are characterized by possibility to calculate their value on a union of multisets by aggregating their values on separate multisets, that makes them easy for parallel computation.
|
| Document Type |
article
|
| Language |
English
Russian |
| Publisher Information |
Ivannikov Institute for System Programming of the Russian Academy of Sciences, 2018.
|
| Subject Terms | |
