Computing Diameters in Slim Graphs

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/255208
Download file(s):
File Description SizeFormat 
255208.pdfFulltext601.53 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Computing Diameters in Slim Graphs
Authors: Block, Benjamin
Milakovic, Michael
Abstract: 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.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2018
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/255208
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.