WEA 2006: Experimental Algorithms pp 98-108

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

• Krists Boitmanis
• Kārlis Freivalds
• Pēteris Lediņš
• Rūdolfs Opmanis
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4007)

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

## Keywords

algorithm engineering analysis of algorithms approximation techniques graph algorithms graph diameter

## References

1. 1.
Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication). SIAM J. on Computing 28, 1167–1181 (1999)
2. 2.
Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An Experimental Comparison of Three Graph Drawing Algorithms. In: Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 306–315 (1995)Google Scholar
3. 3.
Brandstädt, A., Chepoi, V.D., Dragan, F.F.: The Algorithmic Use of Hyper-Tree Structure and Maximum Neighborhood Orderings. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 65–80. Springer, Heidelberg (1995)Google Scholar
4. 4.
Chartrand, G., Lesniak, L.: Graphs & Digraphs. Chapman & Hall, Boca Raton (1996)
5. 5.
Chung, F.R.K.: Diameters of Graphs: Old Problems and New Results. Congressus Numerantium 60, 295–317 (1987)
6. 6.
Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progression. In: Proc 19th ACM Symp on Theory of Computing, pp. 1–6 (1987)Google Scholar
7. 7.
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge (1990)
8. 8.
Corneil, D.G., Dragan, F.F., Köhler, E.: On the Power of BFS to Determine a Graph’s Diameter. Networks 42(4), 209–222 (2003)
9. 9.
Dor, D., Halperin, S., Zwick, U.: All Pairs Almost Shortest Paths. Electronic Colloquium on Computational Complexity 4 (1997)Google Scholar
10. 10.
Dragan, F.F.: Dominating Cliques in Distance-Hereditary Graphs. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol. 824, pp. 370–381. Springer, Heidelberg (1994)Google Scholar
11. 11.
Dragan, F.F., Nicolai, F.: LexBFS-orderings of Distance-Hereditary Graphs with Application to the Diametral Pair Problem. Discrete Appl. Math. 98, 191–207 (2000)
12. 12.
Dragan, F.F., Nicolai, F., Brandstädt, A.: LexBFS-orderings and Powers of Graphs. In: D’Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol. 1197, pp. 166–180. Springer, Heidelberg (1997)Google Scholar
13. 13.
Farley, A.M., Proskurowsky, A.: Computation of the Center and Diameter of Outerplanar Graphs. Discrete Appl. Math. 2, 185–191 (1980)
14. 14.
Handler, G.: Minimax Location of a Facility in an Undirected Tree Graph. Transp. Sci. 7, 287–293 (1973)
15. 15.
Olariu, S.: A Simple Linear-Time Algorithm for Computing the Center of an Interval Graph. Int. J. Comput. Math. 34, 121–128 (1990)
16. 16.
Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic Aspects of Vertex Elimination on Graphs. SIAM J. Comput. 5, 266–283 (1976)
17. 17.
18. 18.
Seidel, R.: On the All-Pair-Shortest-Paths Problem. In: Proc 24th ACM Symp. on Theory of Computing, pp. 745–749 (1992)Google Scholar

## Authors and Affiliations

• Krists Boitmanis
• 1
• Kārlis Freivalds
• 1
• Pēteris Lediņš
• 1
• Rūdolfs Opmanis
• 1
1. 1.Institute of Mathematics and ComputerScienceUniversity of LatviaRigaLatvia