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...
Gespeichert in:
| Datum: | 2004 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Інститут програмних систем НАН України
2004
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/2312 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | 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| _version_ | 1862673227240701952 |
|---|---|
| author | Nepomniaschaya, A.S. Borets, T.V. |
| author_facet | Nepomniaschaya, A.S. Borets, T.V. |
| citation_txt | Checking spanning trees optimality using associative parallel processors and its visualization / A.S. Nepomniaschaya, T.V. Borets // Проблеми програмування. — 2004. — N 2,3. — С. 244-250. — Бібліогр.: 9 назв. — англ. |
| collection | DSpace DC |
| description | 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.
|
| first_indexed | 2025-12-07T15:38:10Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-2312 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | English |
| last_indexed | 2025-12-07T15:38:10Z |
| publishDate | 2004 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Nepomniaschaya, A.S. Borets, T.V. 2008-09-17T13:18:43Z 2008-09-17T13:18:43Z 2004 Checking spanning trees optimality using associative parallel processors and its visualization / A.S. Nepomniaschaya, T.V. Borets // Проблеми програмування. — 2004. — N 2,3. — С. 244-250. — Бібліогр.: 9 назв. — англ. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/2312 681.3 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. This work was supported in part by the Russian Foundation for Basic Research under Grant N 03-01-00399. en Інститут програмних систем НАН України Параллельное программирование Распределенные системы и сети Checking spanning trees optimality using associative parallel processors and its visualization Article published earlier |
| spellingShingle | Checking spanning trees optimality using associative parallel processors and its visualization Nepomniaschaya, A.S. Borets, T.V. Параллельное программирование Распределенные системы и сети |
| title | Checking spanning trees optimality using associative parallel processors and its visualization |
| title_full | Checking spanning trees optimality using associative parallel processors and its visualization |
| title_fullStr | Checking spanning trees optimality using associative parallel processors and its visualization |
| title_full_unstemmed | Checking spanning trees optimality using associative parallel processors and its visualization |
| title_short | Checking spanning trees optimality using associative parallel processors and its visualization |
| title_sort | checking spanning trees optimality using associative parallel processors and its visualization |
| topic | Параллельное программирование Распределенные системы и сети |
| topic_facet | Параллельное программирование Распределенные системы и сети |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/2312 |
| work_keys_str_mv | AT nepomniaschayaas checkingspanningtreesoptimalityusingassociativeparallelprocessorsanditsvisualization AT boretstv checkingspanningtreesoptimalityusingassociativeparallelprocessorsanditsvisualization |