Rendezvous search on labeled networks

TLDR

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 analyze continuous and discrete rendezvous on labelled networks, deriving optimality conditions for asymmetric and symmetric strategies and specializing to interval and circle topologies. We extend Howard’s work for the continuous case and prove a conjecture on the optimal symmetric strategy for the discrete case. © 2002 Wiley Periodicals, Inc.; DOI 10.1002/nav.10011.

Abstract

Abstract 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. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 256–274, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10011