Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for id:"oai:etd.ohiolink.edu:kent1497402176814598". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ 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

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 DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th 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 (7th 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

.