Finding a shortest walk along a sequence of imprecise regions in a graph
Loading...
Date
2019-06
Authors
Sheibani, Nima
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
NP-Hard, Computational geometry, Shortest walk, Imprecise regions, Non-crossing walk, Weakly simple walk, PLANAR 3-SAT, Non-crossing spanning tree