CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Computing giant graph diameters

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
27th International Workshop on Combinatorial Algorithms IWOCA 2016, Lecture Notes in Computer Science Vol. 9843 (2016), p. 373-384 .
[Konferensbidrag, refereegranskat]

This paper is devoted to the fast and exact diameter computation in graphs with n vertices and m edges, if the diameter is a large fraction of n. We give an optimal O(m+n) time algorithm for diameters above n/2. The problem changes its structure at diameter value n/2, as large cycles may be present. We propose a randomized O(m+n log n) time algorithm for diameters above n/3.



Denna post skapades 2016-08-29.
CPL Pubid: 240880