Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2000-10

July 2000

Rendezvous Search on Labelled Networks

Steve Alpern


Two players are independently placed on a commonly labelled network  X.  They cannot see each other but wish to meet in least expected time. We consider continuous and discrete versions, in which they may move at unit speed or between adjacent distinct nodes, respectively. There are two versions of the problem (asymmetric or symmetric) depending on whether or not we allow the players to use different strategies. After obtaining some optimality conditions for general networks, we specialize to the interval and circle networks. In the first setting, we extend the work of J.V. Howard; in the second we prove a conjecture concerning the optimal symmetric strategy.

A compressed (gzip) PostScript file (95 kB) with the contents of this report (sorry, without figures) can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-2000-10, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2000

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html.