Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(geometric intersection graphs)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

University of Waterloo

1.
Skrepetos, Dimitrios.
Shortest Paths in *Geometric* *Intersection* * Graphs*.

Degree: 2018, University of Waterloo

URL: http://hdl.handle.net/10012/13454

This thesis studies shortest paths in geometric intersection graphs, which can model, among others, ad-hoc communication and transportation networks. First, we consider two classical problems in the field of algorithms, namely Single-Source Shortest Paths (SSSP) and All-Pairs Shortest Paths (APSP). In SSSP we want to compute the shortest paths from one vertex of a graph to all other vertices, while in APSP we aim to find the shortest path between every pair of vertices. Although there is a vast literature for these problems in many graph classes, the case of geometric intersection graphs has been only partially addressed.
In unweighted unit-disk graphs, we show that we can solve SSSP in linear time, after presorting the disk centers with respect to their coordinates. Furthermore, we give the first (slightly) subquadratic-time APSP algorithm by using our new SSSP result, bit tricks, and a shifted-grid-based decomposition technique.
In unweighted, undirected geometric intersection graphs, we present a simple and general technique that reduces APSP to static, offline intersection detection. Consequently, we give fast APSP algorithms for intersection graphs of arbitrary disks, axis-aligned line segments, arbitrary line segments, d-dimensional axis-aligned boxes, and d-dimensional axis-aligned unit hypercubes. We also provide a near-linear-time SSSP algorithm for intersection graphs of axis-aligned line segments by a reduction to dynamic orthogonal point location.
Then, we study two problems that have received considerable attention lately. The first is that of computing the diameter of a graph, i.e., the longest shortest-path distance between any two vertices. In the second, we want to preprocess a graph into a data structure, called distance oracle, such that the shortest path (or its length) between any two query vertices can be found quickly. Since these problems are often too costly to solve exactly, we study their approximate versions.
Following a long line of research, we employ Voronoi diagrams to compute a (1+epsilon)-approximation of the diameter of an undirected, non-negatively-weighted planar graph in time near linear in the input size and polynomial in 1/epsilon. The previously best solution had exponential dependency on the latter. Using similar techniques, we can also construct the first (1+epsilon)-approximate distance oracles with similar preprocessing time and space and only O(log(1/ε)) query time.
In weighted unit-disk graphs, we present the first near-linear-time (1+epsilon)-approximation algorithm for the diameter and for other related problems, such as the radius and the bichromatic closest pair. To do so, we combine techniques from computational geometry and planar graphs, namely well-separated pair decompositions and shortest-path separators. We also show how to extend our approach to obtain O(1)-query-time (1+epsilon)-approximate distance oracles with near linear preprocessing time and space. Then, we apply these oracles, along with additional ideas, to build a data…

Subjects/Keywords: shortest paths; unit-disk graphs; planar graphs; geometric intersection graphs; diameter

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Skrepetos, D. (2018). Shortest Paths in Geometric Intersection Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/13454

Not specified: Masters Thesis or Doctoral Dissertation

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

Skrepetos, Dimitrios. “Shortest Paths in Geometric Intersection Graphs.” 2018. Thesis, University of Waterloo. Accessed July 19, 2019. http://hdl.handle.net/10012/13454.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Skrepetos, Dimitrios. “Shortest Paths in Geometric Intersection Graphs.” 2018. Web. 19 Jul 2019.

Vancouver:

Skrepetos D. Shortest Paths in Geometric Intersection Graphs. [Internet] [Thesis]. University of Waterloo; 2018. [cited 2019 Jul 19]. Available from: http://hdl.handle.net/10012/13454.

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Skrepetos D. Shortest Paths in Geometric Intersection Graphs. [Thesis]. University of Waterloo; 2018. Available from: http://hdl.handle.net/10012/13454

Not specified: Masters Thesis or Doctoral Dissertation

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

Degree: 2019, University Utrecht

URL: 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

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 2^{O}(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 2^{o}(n / log n)-time algorithm). These results are surprising, since many (hard) problems can be solved in time 2^{O}(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 2^{O}(n^{1-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 Details Similar Records

❌

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

APA (6^{th} 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 (16^{th} Edition):

van der Zanden, Tom Cornelis. “Theory and Practical Applications of Treewidth.” 2019. Doctoral Dissertation, University Utrecht. Accessed July 19, 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 (7^{th} Edition):

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

Vancouver:

van der Zanden TC. Theory and Practical Applications of Treewidth. [Internet] [Doctoral dissertation]. University Utrecht; 2019. [cited 2019 Jul 19]. 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