Although it was invented by Mikhail Gromov, in 1987, to describe some family of groups[1], the notion of Gromov hyperbolicity has many applications and interpretations in different fields. It has applications in Biology, Networking, Graph Theory, and many other areas of research. The Gromov hyperbolicity constant of several families of graphs and geometric spaces has been determined. However, so far, the only known algorithm for calculating the Gromov hyperbolicity constant δ of a discrete metric space is the brute force algorithm with running time O (n4) using the four-point condition. In this thesis, we first introduce an approximation algorithm which calculates a O (log n)-approximation of the hyperbolicity constant δ, based on a layering approach, in time O(n2), where n is the number of points in the metric space. We also calculate the fixed base point hyperbolicity constant δr for a fixed point r using a (max, min)−matrix multiplication algorithm by Duan in time O(n2.688)[2]. We use this result to present a 2-approximation algorithm for calculating the hyper-bolicity constant in time O(n2.688). We also provide an exact algorithm to compute the hyperbolicity constant δ in time O(n3.688) for a discrete metric space. We then present some partial results we obtained for designing some approximation algorithms to compute the hyperbolicity constant δ.
| Identifer | oai:union.ndltd.org:kaust.edu.sa/oai:repository.kaust.edu.sa:10754/244575 |
| Date | 07 1900 |
| Creators | Ismail, Anas |
| Contributors | Vigneron, Antoine E., Chikalov, Igor, Gao, Xin |
| Source Sets | King Abdullah University of Science and Technology |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Rights | 2013-07-30, At the time of archiving, the student author of this thesis opted to temporarily restrict access to it. The full text of this thesis became available to the public after the expiration of the embargo on 2013-07-30. |
Page generated in 0.0017 seconds