Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/3714
Название: | Efficient Algorithm for Finding Minimal Spanning Tree in Directed Graphs With Integer-Valued Weights |
Авторы: | Tolkacheva, A. |
Дата публикации: | 2011 |
Издатель: | St. Petersburg University Press |
Библиографическое описание: | 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. |
Аннотация: | 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. |
Ключевые слова: | MINIMAL SPANNING TREE DIRECTED GRAPHS EFFICIENT ALGORITHM INTEGER-VALUED WEIGHTS COUNTING SORT RADIX-SORT TIME BOUND |
URI: | http://elar.urfu.ru/handle/10995/3714 |
Конференция/семинар: | V Russian Summer School in Information Retrieval (RuSSIR’2011) V Российская летняя школа по информационному поиску (RuSSIR’2011) EDBT Summer Schools |
Дата конференции/семинара: | 15.08.2011–19.08.2011 |
ISBN: | 978-5-288-05225-5 |
Источники: | RuSSIR/EDBT2011 |
Располагается в коллекциях: | Информационный поиск |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
RuSSIR_2011_08.pdf | 130,91 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.