Search ETDs:
Tree-Like Structure in Graphs and Embedability to Trees
Abu-Ata, Muad Mustafa

, PHD, Kent State University, College of Arts and Sciences / Department of Computer Science.
The problem of embedding a graph metric into a “nice” and “simpler” host metric space with low distortion has been a subject of extensive research, motivated from several applications in various domains. “Nice” metric spaces are those with well-studied structural properties, allowing to design efficient approximation algorithms. Particular host metrics of choice, also favored from the algorithmic point of view, are trees, spanning trees and collection of them.

We investigate the embedability of a graph metric into a tree metric, a spanning tree metric and a collection of them and detect such metric tree-like structure in graphs. First, we investigate few graph parameters which capture and quantify the phenomenon of being metrically close to a tree. By bringing all those parameters together, we not only provide efficient means for detecting such metric tree-like structures in large-scale networks but also show how such structures can be used for fundamental primitives in many data and graph mining algorithms. Also, we present strong evidences that a number of real-life networks, taken from different domains exhibit tree-like structures from a metric point of view.

Second, we study collective tree spanners for graphs enjoying special Robertson Seymour’s tree-decompositions, and demonstrate interesting consequences of obtained results. Specifically, we demonstrate a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative tree t-spanner (NP-hard problem), constructs a system of log2 n collective additive tree O(t log n)-spanners of G. That is, with a slight increase in the number of trees and in the stretch, one can “turn” a multiplicative tree spanner into a small set of collective additive tree spanners. We extend this result to demonstrate that, for every fixed k, there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative t-spanner with tree-width k -1, constructs a system of at most k(1 + log2 n) collective additive tree O(t log n)-spanners of G.

Finally, we provide an efficient algorithm to embed weighted graphs into tree metrics with proven theoretical bounds and good embedding results on real-world datasets.
Feodor Dragan (Advisor)

Recommended Citations

Hide/Show APA Citation

Abu-Ata, M. (). Tree-Like Structure in Graphs and Embedability to Trees. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Abu-Ata, Muad. "Tree-Like Structure in Graphs and Embedability to Trees." Electronic Thesis or Dissertation. Kent State University, . OhioLINK Electronic Theses and Dissertations Center. 23 Oct 2017.

Hide/Show Chicago Citation

Abu-Ata, Muad "Tree-Like Structure in Graphs and Embedability to Trees." Electronic Thesis or Dissertation. Kent State University, . https://etd.ohiolink.edu/

Files

dissertation.pdf (1.34 MB) View|Download