Communications of the ACM
Find Me Quickly
In this cooperative game, two players want to meet each other in a graph as quickly as possible. Meeting each other means both players are at the same node at the same time or traverse an edge in opposite directions in some minute. Each player moves or stays put each minute. A move takes one player from one node across an edge to a neighboring node in the undirected graph.
Warm-up: Suppose the two players are in a graph consisting of a cycle of n nodes (see Figure 1). The nodes are numbered, and each player knows both the topology and the number of the node where he or she is placed. If both players move, say, clockwise, they may never meet. If player A does not move (the "stay-put" strategy) and player B moves in one direction, player B will find player A in n-1 minutes in the worst case. Alternatively, if both agree to move as quickly as possible to some node, say, node 4, and stay there, then the latter of the two will arrive at node 4 in n/2 minutes at most. Is there any other strategy that has a worst-case time complexity of n/2 minutes but also a better average-case time complexity than the go-to-a-common-node strategy?
No entries found