Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/3714
Title: Efficient Algorithm for Finding Minimal Spanning Tree in Directed Graphs With Integer-Valued Weights
Authors: Tolkacheva, A.
Issue Date: 2011
Publisher: St. Petersburg University Press
Citation: 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.
Abstract: 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.
Keywords: 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
Conference name: V Russian Summer School in Information Retrieval (RuSSIR’2011)
V Российская летняя школа по информационному поиску (RuSSIR’2011)
EDBT Summer Schools
Conference date: 15.08.2011–19.08.2011
ISBN: 978-5-288-05225-5
Origin: RuSSIR/EDBT2011
Appears in Collections:Информационный поиск

Files in This Item:
File Description SizeFormat 
RuSSIR_2011_08.pdf130,91 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.