Computing Diameters in Slim Graphs
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2018
Författare
Block, Benjamin
Milakovic, Michael
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
With the use of large graphs with n vertices and m edges, the current approach for computing the diameter is not efficient. We have investigated a special graph class, namely slim graphs. Slim graphs are graphs whose diameter is at least some fixed fraction of the number of vertices. This constraint allows us to prove structural features in these special graphs. Using these features, we have developed three algorithms which are asymptotically superior to diameter computation in the general case. We present the following three algorithms, for a fixed 0 < k < 1/2: a (1 − k)- approximation algorithm of the diameter in O(n+m) time; a deterministic algorithm which computes the diameter in O(n2) time and a Monte Carlo algorithm which also computes the diameter in O(n2) time.
Beskrivning
Ämne/nyckelord
Data- och informationsvetenskap , Computer and Information Science