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:"uu:oai:dspace.library.uu.nl:1874/381134". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. van der Zanden, Tom Cornelis. Theory and Practical Applications of Treewidth.

Degree: 2019, University Utrecht

This thesis studies the theory and practical applications of separator-based dynamic programming (and in particular treewidth) for solving combinatorial problems in graphs. The thesis consists of three parts; the first focusing on graph embedding problems, the second on problems in geometric intersection graphs, and the third explores practical applications of these techniques to, among others, computing game-theoretic centrality measures. In the first part, we study graph embedding problems: given a graph, we want to determine whether it can be embedded into another graph, for instance as a subgraph or minor. We show that several such problems can be solved in time 2O(n / log n) on n-vertex planar graphs and that, assuming the Exponential Time Hypothesis, this running time is optimal (i.e., there is no 2o(n / log n)-time algorithm). These results are surprising, since many (hard) problems can be solved in time 2O(sqrt n) in planar graphs using treewidth-based techniques; graph embedding problems seem to be an exception to this rule. The second part studies problems in geometric intersection graphs. A geometric intersection graph is obtained by taking a collection of objects in d-dimensional space (for instance, unit disks in 2D), and building a graph by taking a vertex corresponding to each object, with edges between each pair of vertices whose corresponding objects intersect. We show that many classical problems (such as independent set, dominating set and Steiner tree) can be solved in time 2O(n1-1/d), and this result is tight under the Exponential Time Hypothesis. To obtain these results, we introduce the notion of weighted clique-partitioned tree decompositions. While geometric intersection graphs can have unbounded treewidth, we show that they (under certain conditions) admit clique-partitioned tree decompositions of small width – and that this fact can be exploited to obtain fast algorithms. The third part explores practical applications of treewidth. As having a suitable tree decomposition is crucial for any such applied use, we first explore how the power of graphics processing units (GPUs) can be used to compute treewidth in parallel. We then study how treewidth can be exploited to compute game-theoretic centrality measures based on the Shapley value in graphs, and show that this can be applied to analyzing terrorist networks to identify the key entities. Advisors/Committee Members: Bodlaender, Hans.

Subjects/Keywords: treewidth; graph theory; exponential time hypothesis; centrality measures; subgraph isomorphism; complexity; algorithms; geometric intersection graphs; Shapley value

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

van der Zanden, T. C. (2019). Theory and Practical Applications of Treewidth. (Doctoral Dissertation). University Utrecht. Retrieved from http://dspace.library.uu.nl/handle/1874/381134 ; URN:NBN:NL:UI:10-1874-381134 ; urn:isbn:978-90-393-7147-3 ; URN:NBN:NL:UI:10-1874-381134 ; http://dspace.library.uu.nl/handle/1874/381134

Chicago Manual of Style (16th Edition):

van der Zanden, Tom Cornelis. “Theory and Practical Applications of Treewidth.” 2019. Doctoral Dissertation, University Utrecht. Accessed July 20, 2019. http://dspace.library.uu.nl/handle/1874/381134 ; URN:NBN:NL:UI:10-1874-381134 ; urn:isbn:978-90-393-7147-3 ; URN:NBN:NL:UI:10-1874-381134 ; http://dspace.library.uu.nl/handle/1874/381134.

MLA Handbook (7th Edition):

van der Zanden, Tom Cornelis. “Theory and Practical Applications of Treewidth.” 2019. Web. 20 Jul 2019.

Vancouver:

van der Zanden TC. Theory and Practical Applications of Treewidth. [Internet] [Doctoral dissertation]. University Utrecht; 2019. [cited 2019 Jul 20]. Available from: http://dspace.library.uu.nl/handle/1874/381134 ; URN:NBN:NL:UI:10-1874-381134 ; urn:isbn:978-90-393-7147-3 ; URN:NBN:NL:UI:10-1874-381134 ; http://dspace.library.uu.nl/handle/1874/381134.

Council of Science Editors:

van der Zanden TC. Theory and Practical Applications of Treewidth. [Doctoral Dissertation]. University Utrecht; 2019. Available from: http://dspace.library.uu.nl/handle/1874/381134 ; URN:NBN:NL:UI:10-1874-381134 ; urn:isbn:978-90-393-7147-3 ; URN:NBN:NL:UI:10-1874-381134 ; http://dspace.library.uu.nl/handle/1874/381134

.