More efficient periodic traversal in anonymous undirected graphs

作     者：Czyzowicz, Jurek Dobrev, Stefan Gasieniec, Leszek Ilcinkas, David Jansson, Jesper Klasing, Ralf Lignos, Ioannis Martin, Russell Sadakane, Kunihiko Sung, Wing-Kin 

作者机构：CNRS LaBRI F-33405 Talence France Univ Bordeaux F-33405 Talence France Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada Slovak Acad Sci Inst Math Bratislava 84000 Slovakia Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Ochanomizu Univ Bunkyo Ku Tokyo 1128610 Japan Univ Durham Dept Comp Sci Durham DH1 3LE England Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan Natl Univ Singapore Dept Comp Sci Singapore 117543 Singapore 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2012年第444卷

页      面：60-76页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Royal Society International Joint Project, IJP [2007/R1] ANR project ALADDIN ANR project ALPAGE INRIA project CEPAGE European project GRAAL European project DYNAMO Special Coordination Funds for Promoting Science and Technology, Japan Nuffield Foundation "The structure and efficient utilization of the Internet and other distributed systems" [NAL/32566] 

主　　题：Algorithms and data structures Graph exploration Periodic graph traversal Oblivious agent Constant-memory agent Three-layer partition 

摘      要：We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it;for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily;see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005)[4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gasieniec et al. (2008) [7] to be no more than 3.75n - 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most (4 + 1/3)n - 4 for oblivious agents and a period length of at most 3.5n - 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n - 2, on the period length for the oblivious case. (c) 2012 Elsevier B.V. All rights reserved.