Paper Info
Title
Linear time and space gathering of anonymous mobile agents in asynchronous trees
Abstract
We investigate the relation between the (ideal) time and space complexities for the gathering problem with k anonymous agents in asynchronous anonymous tree networks. The gathering problem requires that all the agents in the network have to meet at a single node within a finite time. Although an asymptotically space-optimal algorithm is known, its time complexity is quite large. In this paper, we consider asymptotically (ideal-)time-optimal algorithms and investigate the minimum memory requirement per agent for asymptotically time-optimal algorithms. First, we show that there exists a tree with n nodes in which @W(n) bits of memory per agent is required to solve the gathering problem in O(n) time (asymptotically time-optimal). Then, we present an asymptotically time-optimal gathering algorithm. This algorithm can be executed if each agent has O(n) bits of memory. From this lower/upper bound, this algorithm is asymptotically space-optimal on the condition that the time complexity is asymptotically optimal.
Year
DOI
Venue
2013
10.1016/j.tcs.2013.01.022
Theor. Comput. Sci.
Keywords
DocType
Volume
asynchronous tree,asymptotically time-optimal,asymptotically space-optimal algorithm,asymptotically optimal,space gathering,gathering problem,time complexity,finite time,asymptotically time-optimal algorithm,time-optimal algorithm,anonymous mobile agent,linear time,asymptotically space-optimal,asymptotically time-optimal gathering algorithm
Journal
478,
ISSN
Citations 
PageRank 
0304-3975
1
0.35
References 
Authors
13
5
Name
Order
Citations
PageRank
Daisuke Baba1171.74
Tomoko Izumi214121.33
Fukuhito Ooshita323636.40
Hirotsugu Kakugawa427936.35
Toshimitsu Masuzawa563591.06