Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
dissertation.pdf (1001.7 KB)
ETD Abstract Container
Abstract Header
Tree-Breadth of Graphs with Variants and Applications
Author Info
Leitert, Arne
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598
Abstract Details
Year and Degree
2017, PHD, Kent State University, College of Arts and Sciences / Department of Computer Science.
Abstract
The
tree-breadth
of a graph is a recently introduced variant of the well known idea of decomposing a graph into a tree of bags. It is a parameter which adds a metric constraint to tree-decompositions limiting the radius of each bag. In this dissertation, we further investigate the tree-breadth of graphs. We present approaches to compute a tree-decomposition with small breadth for a given graph including approximation algorithms for general graphs as well as optimal solutions for special graph classes. Additionally, we introduce a variant of tree-breadth called
strong tree-breadth
. Next, we present various algorithms to approach the (Connected)
r
-Domination problem for graphs with bounded tree-breadth. One variant, called
path-breadth
, requires the decomposition to be a path instead of a tree. We use graphs with bounded path-breadth to construct efficient constant-factor approximation algorithms for the bandwidth and line-distortion problems. Motivated by these results, we introduce and investigate the new
Minimum Eccentricity Shortest Path
problem. We analyse the hardness of the problem, show algorithms to compute an optimal solution, and present approximation algorithms differing in quality and runtime.
Committee
Feodor Dragan (Advisor)
Subject Headings
Computer Science
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Leitert, A. (2017).
Tree-Breadth of Graphs with Variants and Applications
[Doctoral dissertation, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598
APA Style (7th edition)
Leitert, Arne.
Tree-Breadth of Graphs with Variants and Applications.
2017. Kent State University, Doctoral dissertation.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598.
MLA Style (8th edition)
Leitert, Arne. "Tree-Breadth of Graphs with Variants and Applications." Doctoral dissertation, Kent State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
kent1497402176814598
Download Count:
443
Copyright Info
© 2017, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.