×

DMVP: foremost waypoint coverage of time-varying graphs. (English) Zbl 1417.68048

Kratsch, Dieter (ed.) et al., Graph-theoretic concepts in computer science. 40th international workshop, WG 2014, Nouan-le-Fuzelier, France, June 25–27, 2014. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8747, 29-41 (2014).
Summary: We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents’ navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy \(\mathcal {R} \supset \mathcal {B} \supset \mathcal {P}\) of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in \(\mathcal {R}\), limited approximability in \(\mathcal {B}\), and tractability in \(\mathcal {P}\). We also give topologies in which DMVP in \(\mathcal {R}\) is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.
For the entire collection see [Zbl 1318.68028].

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68R10 Graph theory (including graph drawing) in computer science
68T42 Agent technology and artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv