Topics in graph algorithms

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal Nabih
dc.date.accessioned 2018-04-24T08:17:27Z
dc.date.available 2018-04-24T08:17:27Z
dc.date.copyright 2003 en_US
dc.date.issued 2018-04-24
dc.identifier.uri http://hdl.handle.net/10725/7494
dc.description.abstract Coping with computational intractability has inspired the development of a variety of algorithmic techniques. The main challenge has usually been the design of polynomial time algorithms for NP-complete problems in a way that guarantees some, often worst-case, satisfactory performance when compared to exact (optimal) solutions. We mainly study some emergent techniques that help to bridge the gap between computational intractability and practicality. We present results that lead to better exact and approximation algorithms and better implementations. The problems considered in this dissertation share much in common structurally, and have applications in several scientific domains, including circuit design, network reliability, and bioinformatics. We begin by considering the relationship between graph coloring and the immersion order, a well-quasi-order defined on the set of finite graphs. We establish several (structural) results and discuss their potential algorithmic consequences. We discuss graph metrics such as treewidth and pathwidth. Treewidth is well studied, mainly because many problems that are NP-hard in general have polynomial time algorithms when restricted to graphs of bounded treewidth. Pathwidth has many applications ranging from circuit layout to natural language processing. We present a linear time algorithm to approximate the pathwidth of planar graphs that have a fixed disk dimension. We consider the face cover problem, which has potential applications in facilities location and logistics. Being fixed-parameter tractable, we develop an algorithm that solves it in time O(5k + n2) where k is the input parameter. This is a notable improvement over the previous best known algorithm, which runs in O(8kn). In addition to the structural and algorithmic results, this text tries to illustrate the practicality of fixed-parameter algorithms. This is achieved by implementing some algorithms for the vertex cover problem, and conducting experiments on real data sets. Our experiments advocate the viewpoint that, for many practical purposes, exact solutions of some NP-complete problems are affordable. en_US
dc.language.iso en en_US
dc.title Topics in graph algorithms en_US
dc.type Thesis en_US
dc.title.subtitle structural results and algorithmic techniques, with applications en_US
dc.author.degree PHD en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.description.physdesc x, 112 p: ill en_US
dc.author.advisor Langston, Micheal A.
dc.description.bibliographiccitations Includes bibliographical references en_US
dc.identifier.ctation Khzam, A., & Nabih, F. (2003). Topics in graph algorithms: structural results and algorithmic techniques, with applications. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php en_US
dc.identifier.url http://trace.tennessee.edu/utk_graddiss/1954/ en_US
dc.orcid.id https://orcid.org/0000-0001-5221-8421 en_US
dc.publisher.institution University of Tennessee en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account