Finding a shortest walk along a sequence of imprecise regions in a graph
| dc.contributor.author | Sheibani, Nima | |
| dc.contributor.examiningcommittee | Miller, Avery (Computer Science) Morrison, Jason (Department of Biosystems) | en_US |
| dc.contributor.supervisor | Durocher, Stephane (Computer Science) | en_US |
| dc.date.accessioned | 2019-07-18T20:28:27Z | |
| dc.date.available | 2019-07-18T20:28:27Z | |
| dc.date.issued | 2019-06 | en_US |
| dc.date.submitted | 2019-06-18T22:00:35Z | en |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| dc.description.abstract | Given a sequence of disc-shaped imprecise regions, $R_{1} \ldots R_{k}$, and a graph $G$ drawn in $\mathbb{R}^2$, we consider the problem of finding a shortest walk in $G$ that visits the imprecise regions in order. Specifically, the walk starts at some vertex $v_{1} \in V(G) \cap R_{1}$, follows a sequence of adjacent vertices from $v_{1}$ to some vertex $v_{2} \in V(G) \cap R_{2}$, and so on, until reaching some vertex $v_{k} \in V(G) \cap R_{k}$. We prove that it is NP-hard to decide whether there is a weakly simple walk in $G$ that visits the sequence of imprecise regions in order, answering a special case of an open problem posed by Löffler \cite{loffler2011existence}. Moreover, we present an exact algorithm that finds a shortest walk visiting $R_{1}$ through $R_{k}$ in any graph $G$, when the walk may include crossings. Generally, this algorithm runs in $O(kn^2 + APSP(n,m))$ time, but when the imprecise regions are mutually disjoint the running time reduces to $O(n^2 + APSP(n,m))$ where $APSP$ denotes the time complexity for all-pairs shortest path. Next we present an $O(kn)$ time algorithm that finds a weakly simple walk visiting $R_{1}$ through $R_{k}$ in a graph $G$ drawn in the plane, where $G$ contains a non-crossing spanning tree, and the walk returned is not of minimum length in general. | en_US |
| dc.description.note | October 2019 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/34038 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | NP-Hard | en_US |
| dc.subject | Computational geometry | en_US |
| dc.subject | Shortest walk | en_US |
| dc.subject | Imprecise regions | en_US |
| dc.subject | Non-crossing walk | en_US |
| dc.subject | Weakly simple walk | en_US |
| dc.subject | PLANAR 3-SAT | en_US |
| dc.subject | Non-crossing spanning tree | en_US |
| dc.title | Finding a shortest walk along a sequence of imprecise regions in a graph | en_US |
| dc.type | master thesis | en_US |