Fast and Simple Approximation of the Diameter and
Radius of a Graph
Abstract
The increasing amount of data to be processed by computers has led to
the need for highly efficient algorithms for various computational
problems. Moreover, the algorithms should be as simple as possible to
be practically applicable. In this paper we propose a very simple
approximation algorithm for finding the diameter and the radius of an
undirected graph. The algorithm runs in O(m sqrt(n)) time and gives an
additive error of O(sqrt(n)) for a graph with n vertices and m edges.
Practical experiments show that the results of our algorithm are close
to the optimum and compare favorably to the 2/3-approximation algorithm
for the diameter problem by Aingworth et al.
Click here to go to this
paper at Springer-Verlag
Return to publications
Contact:
Karlis.Freivalds@mii.lu.lv