Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/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://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 | Size | Format | |
---|---|---|---|---|
RuSSIR_2011_08.pdf | 130,91 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.