Computing Diameters in Slim Graphs

dc.contributor.authorBlock, Benjamin
dc.contributor.authorMilakovic, Michael
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T14:45:25Z
dc.date.available2019-07-03T14:45:25Z
dc.date.issued2018
dc.description.abstractWith 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.
dc.identifier.urihttps://hdl.handle.net/20.500.12380/255208
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectData- och informationsvetenskap
dc.subjectComputer and Information Science
dc.titleComputing Diameters in Slim Graphs
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
local.programmeComputer science – algorithms, languages and logic (MPALG), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
255208.pdf
Storlek:
601.53 KB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext