In this paper, some algorithms arepresented for the fast search of center, radius and diameter of weighted graphs on all-pairsshortest path matrix, using features of real-world road networks graphs. They are comparedwith algorithms searching these parameters by simple pass through elements of matrix.
Download file
Counter downloads: 96
- Title Using weighted graphs features for fast searchingtheir parameters
- Headline Using weighted graphs features for fast searchingtheir parameters
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(16)
- Date:
- DOI
Keywords
центр графа, радиус графа, диаметр графа, матрица кратчайших расстояний, взвешенный граф, graph center, graph radius, graph diameter, all-pairs shortest path matrix, graph features, weighted graphAuthors
References
Zwick U. and Shoshan A. All pairs shortest paths in undirected graphs with integer weights // Proc. of the 40th IEEE Symposium on Foundations of Computer Science. Washington: IEEE Computer Society Washington, 1999. P. 605-614.
Galil Z. and Margalit O. All pairs shortest distances for graphs with small integer length edges // Information and Computation. 1977. No. 134. P. 103-139.
Johnson D. B. Efficient algorithms for shortest paths in sparse graph // J. ACM. 1977. No. 24. P. 1-13.
Using weighted graphs features for fast searchingtheir parameters | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 2(16).
Download full-text version
Download fileCounter downloads: 214