Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Abdulhakeem Mohammed Dissertation.pdf (1.32 MB)

ETD Abstract Container

Abstract Header

Slimness, Thinness and other Negative Curvature Parameters of Graphs

Mohammed, Abdulhakeem Othman
http://rave.ohiolink.edu/etdc/view?acc_num=kent1561995374485276

Abstract Details

2019, PHD, Kent State University, College of Arts and Sciences / Department of Computer Science.
Recently, there has been extensive research on negative\ curvature (or hyperbolicity) of graphs, which measures the local deviation of a metric from a tree metric. In case of graphs (and general geodesic metric spaces), there exist several equivalent definitions of negative curvature parameters involving different but comparable values (they are within small constant factors from each other). In our research, we further study these parameters, and mostly we are investigating in the Rips’ condition involving geodesic triangles, notion of slimness and thinness. We establish a relationship between slimness (and thinness) and other tree-likeness structure parameters including cluster-diameter Delta(G) of a layering partition, tree-length tl(G), and tree-breadth tb(G). We show a relationship between chordality and both slimness and thinness. We present sharp bounds on slimness and thinness of some structured classes of graphs such as AT-free graphs and HHD-free graphs. Additionally, we show that the slimness of every 4-chordal graph is at most 2 and characterize those 4-chordal graphs for which the slimness of every of its induced subgraph is at most 1. More interestingly, we provide exact and approximation algorithms for computing the slimness and thinness. Particularly, an algorithm computing the exact thinness of graphs runs in O(n^2m) time, an 8-approximation algorithm (with additive surplus 4) runs in O(n^2) time (provided the distance matrix is known in advance) and a 3-approximation algorithm runs in O(n^3) time. We present an algorithm to compute the exact slimness of graphs in O(n^4) time, a 24-approximation algorithm (with additive surplus 3) running in O(n^2) time (provided the distance matrix is known in advance) and an 8-approximation algorithm running in O(n^3) time. Additionally, we propose an efficient practical algorithm for computing the exact slimness in graphs using several tricks. The practical algorithm runs in O(n^3m) time in the worst case; however, in practice it runs much faster as we observed in our experiments. Furthermore, we also propose a linear time heuristic algorithm that can be used to estimate the slimness of large graphs and it can also be used as a lower bound for the slimness of graphs. We evaluate our algorithms on real-world networks. Finally, we address some algorithmic applications of negative curvature parameters. We show that the Minimum Eccentricity Shortest Path (MESP) problem can be solved in O(n^{4delta+4}) time (O(n^{2delta+4}) time) for graphs with \delta-slim triangles (delta-thin triangles, respectively), which is NP-complete in general graph. Additionally, we provide an efficient approximation algorithm running in O(n^3) time to compute the MESP problem in hyperbolic graphs. For delta-hyperbolic graphs we get an additive error of at most 2delta. Similarly, for graphs with \delta-slim triangles (delta-thin triangles) we get an additive error of at most 2delta (delta, respectively). Also, we present a linear time algorithm to approximate the diameter, radius and the eccentricities of all vertices in graphs with delta-slim triangles with additive errors linearly depending on \delta. Moreover, we analyze the performance of our approximation algorithm on a set of large real-world networks.
Feodor Dragan (Advisor)
159 p.
Computer Science
Negative Curvature Parameters, Hyperbolicity, Slimness, Thinness

Recommended Citations

Citations

  • Mohammed, A. O. (2019). Slimness, Thinness and other Negative Curvature Parameters of Graphs [Doctoral dissertation, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1561995374485276

    APA Style (7th edition)

  • Mohammed, Abdulhakeem. Slimness, Thinness and other Negative Curvature Parameters of Graphs. 2019. Kent State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1561995374485276.

    MLA Style (8th edition)

  • Mohammed, Abdulhakeem. "Slimness, Thinness and other Negative Curvature Parameters of Graphs." Doctoral dissertation, Kent State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=kent1561995374485276

    Chicago Manual of Style (17th edition)

kent1561995374485276
449
© 2019, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.