Abstract
Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We present fast deterministic algorithms for this rendezvous problem.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpern, S.: The rendezvous search problem. SIAM J. on Control and Optimization 33(3), 673–683 (1995)
Alpern, S.: Rendezvous search on labelled networks. Naval Reaserch Logistics 49, 256–274 (2002)
Alpern, S., Gal, S.: The theory of search games and rendezvous. Int. Series in Operations research and Management Science, vol. 55. Kluwer Academic Publishers, Dordrecht (2002)
Alpern, J., Baston, V., Essegaier, S.: Rendezvous search on a graph. Journal of Applied Probability 36(1), 223–231 (1999)
Alpern, S., Gal, S.: Rendezvous search on the line with distinguishable players. SIAM J. on Control and Optimization 33, 1270–1276 (1995)
Anderson, E., Weber, R.: The rendezvous problem on discrete locations. Journal of Applied Probability 28, 839–851 (1990)
Anderson, E., Essegaier, S.: Rendezvous search on the line with indistinguishable players. SIAM J. on Control and Optimization 33, 1637–1642 (1995)
Anderson, E., Fekete, S.: Asymmetric rendezvous on the plane. In: Proc. 14th Annual ACM Symp. on Computational Geometry (1998)
Anderson, E., Fekete, S.: Two-dimensional rendezvous search. Operations Research 49, 107–118 (2001)
Baston, V., Gal, S.: Rendezvous on the line when the players’ initial distance is given by an unknown probability distribution. SIAM J. on Control and Optimization 36, 1880–1889 (1998)
Baston, V., Gal, S.: Rendezvous search when marks are left at the starting points. Naval Res. Log. 48, 722–731 (2001)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous oblivious robots with limited visibility. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 247–258. Springer, Heidelberg (2001)
Gal, S.: Rendezvous search on the line. Operations Research 47, 974–976 (1999)
Howard, J.: Rendezvous search on the interval and circle. Operation research 47(4), 550–558 (1999)
Lim, W., Alpern, S.: Minimax rendezvous on the line. SIAM J. on Control and Optimization 34(5), 1650–1665 (1996)
Schelling, T.: The strategy of conflict. Oxford University Press, Oxford (1960)
Thomas, L.: Finding your kids when they are lost. Journal on Operational Res. Soc. 43, 637–639 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dessmark, A., Fraigniaud, P., Pelc, A. (2003). Deterministic Rendezvous in Graphs. In: Di Battista, G., Zwick, U. (eds) Algorithms - ESA 2003. ESA 2003. Lecture Notes in Computer Science, vol 2832. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39658-1_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-39658-1_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20064-2
Online ISBN: 978-3-540-39658-1
eBook Packages: Springer Book Archive