Advanced search options

You searched for `id:"oai:etd.ohiolink.edu:kent1497402176814598"`

. One record found.

▼ Search Limiters

Kent State University

1. Leitert, Arne. Tree-Breadth of Graphs with Variants and Applications.

Degree: PhD, College of Arts and Sciences / Department of Computer Science, 2017, Kent State University

URL: http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598

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.
*Advisors/Committee Members: Dragan, Feodor (Advisor).*

Subjects/Keywords: Computer Science

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Leitert, A. (2017). Tree-Breadth of Graphs with Variants and Applications. (Doctoral Dissertation). Kent State University. Retrieved from http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598

Chicago Manual of Style (16^{th} Edition):

Leitert, Arne. “Tree-Breadth of Graphs with Variants and Applications.” 2017. Doctoral Dissertation, Kent State University. Accessed September 24, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598.

MLA Handbook (7^{th} Edition):

Leitert, Arne. “Tree-Breadth of Graphs with Variants and Applications.” 2017. Web. 24 Sep 2017.

Vancouver:

Leitert A. Tree-Breadth of Graphs with Variants and Applications. [Internet] [Doctoral dissertation]. Kent State University; 2017. [cited 2017 Sep 24]. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598.

Council of Science Editors:

Leitert A. Tree-Breadth of Graphs with Variants and Applications. [Doctoral Dissertation]. Kent State University; 2017. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598