Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aaron, E., Kranakis, E., Krizanc, D.: On the complexity of the multi-robot, multi-depot map visitation problem. In: IEEE MASS, pp. 795–800 (2011)
Aaron, E., Krizanc, D., Meyerson, E.: DMVP: foremost waypoint coverage of time-varying graphs (2014). http://arxiv.org/abs/1407.7279
Ahr, D., Reinhelt, G.: A tabu search algorithm for the min-max k-Chinese postman problem. Comput. Oper. Res. 33(12), 3403–3422 (2006)
Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3(2), 73–76 (1980)
Baumann, H., Crescenzi, P., Fraigniaud, P.: Parsimonious flooding in dynamic graphs. Distrib. Comput. 24(1), 31–44 (2011)
Bellman, R.: Dynamic programming treatment of the travelling salesman problem. JACM 9(1), 61–63 (1962)
Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of 26th STOC, pp. 163–171 (1994)
Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Deterministic computations in time-varying graphs: broadcasting under unstructured mobility. In: Calude, C.S., Sassone, V. (eds.) TCS 2010. IFIP AICT, vol. 323, pp. 111–124. Springer, Heidelberg (2010)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. IJPED 27(5), 387–408 (2012)
Avin, C., Koucký, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 121–132. Springer, Heidelberg (2008)
Choset, H.: Coverage for robotics: a survey of recent results. Ann. Math. AI 31, 113–126 (2001)
Correll, N., Rutishauser, S., Martinoli, A.: Comparing coordination schemes for miniature robotic swarms. In: Springer Tracts in Advanced Robotics, vol. 39, pp. 471–480 (2008)
Easton, K., Burdick, J.: A coverage algorithm for multi-robot boundary inspection. In: Proceedings of ICRA, pp. 727–734 (2005)
Edmonds, J., Johnson, E.: Matching, Euler tours and the Chinese postman problem. Math. Program. 5, 88–124 (1973)
Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairman problem. In: Proceedings of 39th STOC (2007)
Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theor. Comput. Sci. 469, 53–68 (2013)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Hopcroft, J., Karp, R.: An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)
Ilcinkas, D., Wade, A.M.: On the power of waiting when exploring public transportation systems. In: Fernàndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol. 7109, pp. 451–464. Springer, Heidelberg (2011)
Ilcinkas, D., Wade, A.M.: Exploration of the T-interval-connected dynamic graphs: the case of the ring. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 13–23. Springer, Heidelberg (2013)
Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: ACM Symposium on Theory of Computing (2010)
Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. ACM SIGACT News 42(1), 82–96 (2011)
Mans, B., Mathieson, L.: On the treewidth of dynamic graphs. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 349–360. Springer, Heidelberg (2013)
Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 553–564. Springer, Heidelberg (2014)
Wagner, A., Lindenbaum, M., Bruckstein, A.: Distributed covering by ant-robots using evaporating traces. IEEE Trans. Robot. Autom. 15(5), 918–933 (1999)
Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. IJ Found. Comput. Sci. 14(02), 267–285 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Aaron, E., Krizanc, D., Meyerson, E. (2014). DMVP: Foremost Waypoint Coverage of Time-Varying Graphs. In: Kratsch, D., Todinca, I. (eds) Graph-Theoretic Concepts in Computer Science. WG 2014. Lecture Notes in Computer Science, vol 8747. Springer, Cham. https://doi.org/10.1007/978-3-319-12340-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-12340-0_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12339-4
Online ISBN: 978-3-319-12340-0
eBook Packages: Computer ScienceComputer Science (R0)