Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Althoubi Asaad.pdf (1.74 MB)

ETD Abstract Container

Abstract Header

An Analysis of one approximation algorithm for graph linearization

Althoubi, Asaad Y
http://orcid.org/0000-0001-9434-1284
http://rave.ohiolink.edu/etdc/view?acc_num=kent1493052478987958

Abstract Details

2017, MS, Kent State University, College of Arts and Sciences / Department of Computer Science.
The Minimum Eccentricity Shortest Path (MESP) Problem consists of determining a shortest path (a path of minimum length between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert who described a linear time approximation algorithm for the problem. A minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line. MESP-problem is NP-hard on general graphs, but it can be solved in linear time for trees. In this thesis, we implement this approximation algorithm for MESP and the algorithm that uses a small eccentricity shortest path found to perform a graph linearization. We analyze their performances on synthetic (generated) graphs, such as interval graphs and proper interval graphs and on real-world networks, such as Gene-to-Gene Networks (GGI), Protein-to-Protein Networks (PPI), Yeast Network, US Air Transportation, the Internet at the Autonomous System, and World-Wide-Web. We have observed that embedding into the line gives a good approximation for the bandwidth problem in terms of maximum and average bandwidth. Moreover, we revealed that the length of a shortest path obtained by the MESP algorithm impacts the maximum and average bandwidth. Additionally, regarding synthetic graphs, we have seen that maximum bandwidth and average bandwidth calculated from embedding into the line increase or decrease according to the change in length of intervals in proper interval graphs and degree sequence in interval graphs. Also, we have noticed that the embedding of proper interval graphs into the line resembles a proper interval ordering of its vertices known from the literature.
Dragan Feodor (Advisor)
Peyravi Hassan (Committee Member)
Sharma Gokarna (Committee Member)
59 p.
Computer Science
Graph linearization, Minimum Eccentricity Shortest Path

Recommended Citations

Citations

  • Althoubi, A. Y. (2017). An Analysis of one approximation algorithm for graph linearization [Master's thesis, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1493052478987958

    APA Style (7th edition)

  • Althoubi, Asaad. An Analysis of one approximation algorithm for graph linearization. 2017. Kent State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1493052478987958.

    MLA Style (8th edition)

  • Althoubi, Asaad. "An Analysis of one approximation algorithm for graph linearization." Master's thesis, Kent State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1493052478987958

    Chicago Manual of Style (17th edition)

kent1493052478987958
474
© 2017, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.