Polynomial deterministic rendezvous in arbitrary graphs

摘要: The rendezvous problem in graphs has been extensively studied the literature, mainly using a randomized approach Two mobile agents have to meet at some node of connected graph We study deterministic algorithms for this problem, assuming that distinct identifiers and are located nodes an unknown anonymous Startup times arbitrarily decided by adversary measure performance algorithm is its cost: given initial location graph, number steps since startup later agent until achieved Deterministic previously shown feasible arbitrary [16] but proposed had cost exponential n smaller identifier l, polynomial difference τ between following was stated [16]: Does there exist with n, labels L1, L2 (or even log L2)? give positive answer both problems: our main result l also show lower bound Ω (n2) on family graphs.