Advertisement

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 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

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)CrossRefMathSciNetzbMATHGoogle Scholar
  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)zbMATHGoogle Scholar
  5. 5.
    Chung, F.R.K.: Diameters of Graphs: Old Problems and New Results. Congressus Numerantium 60, 295–317 (1987)MathSciNetGoogle Scholar
  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)zbMATHGoogle Scholar
  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)CrossRefMathSciNetzbMATHGoogle Scholar
  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)CrossRefMathSciNetzbMATHGoogle Scholar
  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)CrossRefMathSciNetzbMATHGoogle Scholar
  14. 14.
    Handler, G.: Minimax Location of a Facility in an Undirected Tree Graph. Transp. Sci. 7, 287–293 (1973)CrossRefMathSciNetGoogle Scholar
  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)CrossRefMathSciNetzbMATHGoogle Scholar
  16. 16.
    Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic Aspects of Vertex Elimination on Graphs. SIAM J. Comput. 5, 266–283 (1976)CrossRefMathSciNetzbMATHGoogle Scholar
  17. 17.
    Sedgewick, R.: Algorithms in C, Part 5: Graph Algorithms, 3rd edn. Addison-Wesley, Reading (2002)Google Scholar
  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

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

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

Personalised recommendations