Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


dissertation.pdf (1.34 MB)

ETD Abstract Container

Abstract Header

Tree-Like Structure in Graphs and Embedability to Trees

Abu-Ata, Muad Mustafa
http://rave.ohiolink.edu/etdc/view?acc_num=kent1397345185

Abstract Details

, 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)
Computer Science

Recommended Citations

Citations

  • Abu-Ata, M. M. (n.d.). Tree-Like Structure in Graphs and Embedability to Trees [Doctoral dissertation, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1397345185

    APA Style (7th edition)

  • Abu-Ata, Muad. Tree-Like Structure in Graphs and Embedability to Trees. Kent State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1397345185.

    MLA Style (8th edition)

  • Abu-Ata, Muad. "Tree-Like Structure in Graphs and Embedability to Trees." Doctoral dissertation, Kent State University. Accessed JUNE 10, 2025. http://rave.ohiolink.edu/etdc/view?acc_num=kent1397345185

    Chicago Manual of Style (17th edition)

kent1397345185
1,639
© , some rights reserved.Creative Commons License Tree-Like Structure in Graphs and Embedability to Trees by Muad Mustafa Abu-Ata is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by Kent State University and OhioLINK.
Release 3.2.12