|
Upravlenie Bol'shimi Sistemami, 2013, Issue 42, Pages 153–172
(Mi ubs665)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Information Technology Applications in Control
Fast search algorithms for two metric characteristics problems on weighted graphs
A. R. Urakov, T. V. Timeryaev Ufa State Aviation Technical UniversityNPO Saturn
Abstract:
Two problems are considered of metric characteristics search on weighted undirected graphs with non-negative edge weights. The first problem is to find the radius, diameter, at least one center, and one pair of peripheral vertices of an undirected graph with non-negative edge weights. In the second problem one also has the pre-calculated distances matrix. For these problems we propose fast search algorithms, which use only small fraction of graph vertices for metric characteristics search. The proposed algorithms are tested on various inputs against the other popular methods.
Keywords:
metric characteristics of a graph, graph radius, graph diameter, graph center, graph peripheral vertices.
Citation:
A. R. Urakov, T. V. Timeryaev, “Fast search algorithms for two metric characteristics problems on weighted graphs”, UBS, 42 (2013), 153–172
Linking options:
https://www.mathnet.ru/eng/ubs665 https://www.mathnet.ru/eng/ubs/v42/p153
|
Statistics & downloads: |
Abstract page: | 207 | Full-text PDF : | 174 | References: | 36 | First page: | 2 |
|