Efficient Algorithm for Finding Minimal Spanning Tree in Directed Graphs With Integer-Valued Weights
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Efficient Algorithm for Finding Minimal Spanning Tree in Directed Graphs With Integer-Valued Weights
|
|
| Автор |
Tolkacheva, A.
|
|
| Тематика |
MINIMAL SPANNING TREE
DIRECTED GRAPHS EFFICIENT ALGORITHM INTEGER-VALUED WEIGHTS COUNTING SORT RADIX-SORT TIME BOUND |
|
| Описание |
In this paper the task of finding minimal spanning tree in a weighted directed graphs is considered. Here the short survey of existed algorithms solving the given problem with various complexities is conducted. A comparatively simple algorithm that solves the given problem for graphs with integer-valued weights of arcs with the time complexity O(m+nlog n) is developed as well. This result was get because of using radix sort instead of sort by comparison. |
|
| Дата |
2011-10-12T10:41:14Z
2011-10-12T10:41:14Z 2011 |
|
| Тип |
Article
Journal article (info:eu-repo/semantics/article) Published version (info:eu-repo/semantics/publishedVersion) |
|
| Идентификатор |
Tolkacheva A. Efficient Algorithm for Finding Minimal Spanning Tree in Directed Graphs With Integer-Valued Weights / A. Tolkacheva // Web of Data: The joint RuSSIR/EDBT 2011 Summer School, August 15–19, 2011, Proceedings of the Fifth Russian Young Scientists Conference in Information Retrieval / B. Novikov, P. Braslavsky (Eds.). — St. Petersburg, 2011 — P. 72-80.
978-5-288-05225-5 http://elar.urfu.ru/handle/10995/3714 |
|
| Язык |
en
|
|
| Связанные ресурсы |
RuSSIR/EDBT2011
|
|
| Формат |
134050 bytes
application/pdf |
|
| Издатель |
St. Petersburg University Press
|
|