Checking spanning trees optimality using associative parallel processors and its visualization
In this paper, by means of an abstract model of the SIMD type with vertical data processing (the STAR-machine), we present a simple associative parallel algorithm for implementing the criterion of Chin and Houck to verify minimal spanning trees in undirected graphs. This algorithm is given as the...
Saved in:
| Date: | 2004 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут програмних систем НАН України
2004
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/2312 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Checking spanning trees optimality using associative parallel processors and its visualization / A.S. Nepomniaschaya, T.V. Borets // Проблеми програмування. — 2004. — N 2,3. — С. 244-250. — Бібліогр.: 9 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Summary: | In this paper, by means of an abstract model of the SIMD type with vertical data processing (the STAR-machine), we present a simple
associative parallel algorithm for implementing the criterion of Chin and Houck to verify minimal spanning trees in undirected graphs. This
algorithm is given as the corresponding STAR procedure CST whose correctness is proved and time complexity is evaluated. We also provide
an experiment of verifying two spanning trees for optimality in a given undirected graph.
|
|---|---|
| ISSN: | 1727-4907 |