@inproceedings{oai:nitech.repo.nii.ac.jp:00005908,
 author = {Izumi, Tomoko and Izumi, Taisuke and Kamei, Sayaka and Ooshita, Fukuhito},
 book = {Lecture Notes in Computer Science},
 month = {Apr},
 note = {application/pdf, The gathering problem of anonymous and oblivious mobile robots isone of fundamental problems in the theoretical mobile robotics. We consider thegathering problem in unoriented and anonymous rings, which requires that allrobots gather at a non-predefined node. Since the gathering problem cannot besolved without any additional capability to robots, all the previous works assumesome capability of robots, such as accessing the memory on node. In this paper,we focus on the multiplicity capability. This paper presents a deterministic gatheringalgorithm with local-weak multiplicity, which provides the robot with theinformation about whether its current node has more than one robot or not. Thisassumption is strictly weaker than that by previous works. Moreover, we showthat our algorithm is asymptotically time-optimal one, that is, the time complexityof our algorithm is O(n), where n is the number of nodes. Interestingly, inspite of assuming the weaker assumption, it achieves significant improvementcompared to the previous algorithm, which takes O(kn) time for k robots., The original publication will be available at www.springerlink.comLNCS series17th International Colloquium on Structural Information and Commuication Complexity},
 pages = {101--113},
 publisher = {Springer},
 title = {Mobile Robots Gathering Algorithm with Local Weak Multiplicity in Rings},
 volume = {6058},
 year = {2010}
}