Faster treasure hunt and better strongly universal exploration sequences
作者： Qin Xin
DOI: 10.1007/978-3-540-77120-3_48
关键词:
摘要: We study the explicit deterministic treasure hunt problem in an n-vertex network. This was firstly introduced by Ta-Shma, and Zwick [9] [SODA'07]. It is variant of well known rendezvous which one robot (the treasure) always stationary. obtain O(nc(1+ 1/λ))- time solution for this problem, significantly improves currently best result running O(n2c) [9], where c a fixed constant from construction universal exploration sequence [8,9], λ integer ≫ 1. The motivates strongly sequences. give better sequences than [9].
arxiv.org
springer.com
sci-hub.st 参考文章(11)
Dariusz R. Kowalski, Andrzej Pelc, Polynomial deterministic rendezvous in arbitrary graphs international symposium on algorithms and computation. ,vol. 3341, pp. 644- 656 ,(2004) , 10.1007/978-3-540-30551-4_56
Andrzej Pelc, Dariusz Kowalski, Rudolf Fleischer, Gerhard Trippen, Polynomial deterministic rendezvous in arbitrary graphs Untitled Event. pp. 644- 656 ,(2004)
Deterministic Rendezvous in Graphs european symposium on algorithms. ,vol. 2832, pp. 184- 195 ,(2003) , 10.1007/B13632
Don Coppersmith, Prasad Tetali, Peter Winkler, Collisions among random walks on a graph SIAM Journal on Discrete Mathematics. ,vol. 6, pp. 363- 374 ,(1993) , 10.1137/0406029
Anders Dessmark, Pierre Fraigniaud, Dariusz R. Kowalski, Andrzej Pelc, Deterministic Rendezvous in Graphs Algorithmica. ,vol. 46, pp. 69- 96 ,(2006) , 10.1007/S00453-006-0074-2
Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Ugo Vaccaro, Asynchronous deterministic rendezvous in graphs Theoretical Computer Science. ,vol. 355, pp. 315- 326 ,(2006) , 10.1016/J.TCS.2005.12.016
Dariusz R. Kowalski, Adam Malinowski, How to meet in anonymous network international conference on structural information and communication complexity. ,vol. 399, pp. 141- 156 ,(2006) , 10.1016/J.TCS.2008.02.010
Michal Koucký, Universal traversal sequences with backtracking conference on computational complexity. ,vol. 65, pp. 717- 726 ,(2001) , 10.1016/S0022-0000(02)00023-5
Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). pp. 218- 223 ,(1979) , 10.1109/SFCS.1979.34
Omer Reingold, Undirected ST-connectivity in log-space Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05. pp. 376- 385 ,(2005) , 10.1145/1060590.1060647