6533b7d1fe1ef96bd125cae6

RESEARCH PRODUCT

Fast and Simple Approximation of the Diameter and Radius of a Graph

Kārlis FreivaldsPēteris LediņšKrists BoitmanisRūdolfs Opmanis

subject

CombinatoricsTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYGraph (abstract data type)Approximation algorithmAlgorithm engineeringRadiusComputational problemStrength of a graphDistanceMathematicsofComputing_DISCRETEMATHEMATICSAnalysis of algorithmsMathematics

description

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 [1].

yearjournalcountryeditionlanguage
2006-01-01
https://doi.org/10.1007/11764298_9