On temporal graph exploration

Journal of Computer and System Sciences - Tập 119 - Trang 1-18 - 2021
Thomas Erlebach1, Michael Hoffmann1, Frank Kammer2
1School of Informatics, University of Leicester, England, United Kingdom
2THM, University of Applied Sciences Mittelhessen, Germany

Tài liệu tham khảo

Erlebach, 2015, On temporal graph exploration, vol. 9134, 444 Casteigts, 2012, Time-varying graphs and dynamic networks, Int. J. Parallel Emerg. Distrib. Syst., 27, 387, 10.1080/17445760.2012.668546 Lynch, 1996 Michail, 2016, An introduction to temporal graphs: an algorithmic perspective, Internet Math., 12, 239, 10.1080/15427951.2016.1177801 Scheideler, 2002, Models and techniques for communication in dynamic networks, vol. 2285, 27 Berman, 1996, Vulnerability of scheduled networks and a generalization of Menger's theorem, Networks, 28, 125, 10.1002/(SICI)1097-0037(199610)28:3<125::AID-NET1>3.0.CO;2-P Bui-Xuan, 2003, Computing shortest, fastest, and foremost journeys in dynamic networks, Int. J. Found. Comput. Sci., 14, 267, 10.1142/S0129054103001728 Michail, 2016, Traveling salesman problems in temporal graphs, Theor. Comput. Sci., 634, 1, 10.1016/j.tcs.2016.04.006 Casteigts, 2014, Measuring temporal lags in delay-tolerant networks, IEEE Trans. Comput., 63, 397, 10.1109/TC.2012.208 Liu, 2009, Scalable routing in cyclic mobile networks, IEEE Trans. Parallel Distrib. Syst., 20, 1325, 10.1109/TPDS.2008.218 Ajtai, 1982, Largest random component of a k-cube, Combinatorica, 2, 1, 10.1007/BF02579276 Karlin, 1994, On the fault tolerance of the butterfly, 125 Kesten, 1980, The critical probability of bond percolation on the square lattice equals 12, Commun. Math. Phys., 74, 41, 10.1007/BF01197577 Bermond, 1995, Fast gossiping by short messages, vol. 944, 135 Chlebus, 2002, Gossiping to reach consensus, 220 Hromkovic, 2005, Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance Shannon, 1951, Presentation of a maze-solving machine, 173 Bender, 1998, The power of a pebble: exploring and mapping directed graphs, 269 Biswas, 2015, Restricted shortest path in temporal graphs, vol. 9261, 13 Kempe, 2002, Connectivity and inference problems for temporal networks, J. Comput. Syst. Sci., 64, 820, 10.1006/jcss.2002.1829 Mertzios, 2013, Temporal network optimization subject to connectivity constraints, vol. 7966, 657 Brodén, 2004, Online and offline algorithms for the time-dependent TSP with time zones, Algorithmica, 39, 299, 10.1007/s00453-004-1088-z Flocchini, 2009, Exploration of periodically varying graphs, vol. 5878, 534 Ilcinkas, 2018, Exploration of the t-interval-connected dynamic graphs: the case of the ring, Theory Comput. Syst., 62, 1144, 10.1007/s00224-017-9796-3 Di Luna, 2016, Live exploration of dynamic rings, 570 Ilcinkas, 2014, Exploration of constantly connected dynamic graphs based on cactuses, vol. 8576, 250 Erlebach, 2019, Two moves per time step make a difference, vol. 132, 141:1 Avin, 2018, Cover time and mixing time of random walks on dynamic graphs, Random Struct. Algorithms, 52, 576, 10.1002/rsa.20752 Diestel, 2010, Graph Theory, vol. 173 Garey, 1976, The planar hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 704, 10.1137/0205049 Frederickson, 1987, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput., 16, 1004, 10.1137/0216064 Kloks, 1994, Treewidth, Computations and Approximations, vol. 842 Scheffler, 1994 Lipton, 1979, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177, 10.1137/0136016 Gallager, 1983, A distributed algorithm for minimum-weight spanning trees, ACM Trans. Program. Lang. Syst., 5, 66, 10.1145/357195.357200