1. Tracking Paths.
- Author
-
Banik, Aritra, Katz, Matthew J., Packer, Eli, and Simakov, Marina
- Subjects
- *
OBJECT tracking (Computer vision) , *TRACKING algorithms , *APPROXIMATION algorithms , *ARTIFICIAL satellite tracking - Abstract
We consider several problems dealing with tracking of moving objects (e.g., vehicles) in networks. Given a graph G = (V , E) and two vertices s , t ∈ V , a set of vertices T ⊆ V is a tracking set for G (w.r.t. paths from s to t), if one can distinguish between any two paths from s to t by the order in which the vertices of T appear (or do not appear) in them. We prove that the problem of finding a minimum-cardinality tracking set w.r.t. shortest paths from s to t is NP-hard and even APX-hard. On the other hand, for the common case where G is planar, we present a 2-approximation algorithm for this problem. We also describe how to preprocess G (and its tracking set w.r.t. shortest paths from s to t), so that given a sequence of visited trackers, one can reconstruct the traversed path P in O (| P |) time. Moreover, we consider the following related problem: Given a graph G , two vertices s and t , and a set of forbidden vertices F ⊆ V − { s , t } , find a minimum-cardinality set of trackers V ∗ ⊂ V , such that a shortest path P from s to t passes through a forbidden vertex if and only if it passes through a vertex of V ∗. We present a polynomial-time (exact) algorithm for this problem. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF