Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://hdl.handle.net/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://hdl.handle.net/10995/3714
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.pdf130,91 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.