Article

Deterministic rendezvous, treasure hunts and strongly universal exploration sequences

Authors:

Amnon Ta-Shma,

Uri ZwickAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 599 - 608

Published: 07 January 2007 Publication History

Get Access

Abstract

We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open in a recent paper by Dessmark et al. We also introduce an interesting variant of the rendezvous problem which we call the deterministic treasure hunt problem. Both the rendezvous and the treasure hunt problems motivate the study of universal traversal sequences and universal exploration sequences with some strengthened properties. We call such sequences strongly universal traversal (exploration) sequences. We give an explicit construction of strongly universal exploration sequences. The existence of strongly universal traversal sequences, as well as the solution of the most difficult variant of the deterministic treasure hunt problem, are left as intriguing open problems.

References

[1]

{AKL+79} R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Backoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Proc. of the 20th FOCS, pages 218--223, 1979.

Google Scholar

[2]

{ASOO} N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 2000.

Google Scholar

[3]

{CTW93} D. Coppersmith, P. Tetali, and P. Winkler. Collisions among random walks on a graph. SIAM Journal on Discrete Mathematics, 6(3):363--374, 1993.

Digital Library

Google Scholar

[4]

{DFKP06} A. Dessmark, P. Fraigniaud, D. Kowalski, and A. Pelc. Deterministic rendezvous in graphs. Algorithmica, 2006. Online publication June 19, 2006.

Digital Library

Google Scholar

[5]

{DFP03} A. Dessmark, P. Fraigniaud, and A. Pelc. Deterministic rendezvous in graphs. In Proc. of 11th ESA, pages 184--195, 2003.

Google Scholar

[6]

{DGK+06} G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, and U. Vaccaro. Asynchronous deterministic rendezvous in graphs. Theoretical Computer Science, 355(3):315--326, 2006.

Digital Library

Google Scholar

[7]

{EL75} P. Erdös and L. Lovasz. Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal et al., editors, Infinite and Finite Sets, volume 11 of Colloq. Math. Soc. Janos Bolyai, pages 609--627. North-Holland, 1975.

Google Scholar

[8]

{KM06} D. R. Kowalski and A. Malinowski. How to meet in anonymous network. In Proc. of 13th SIROCCO, pages 44--58, 2006.

Digital Library

Google Scholar

[9]

{Kou02} M. Koucký. Universal traversal sequences with backtracking. Journal of Computer and System Sciences, 65(4):717--726, 2002.

Digital Library

Google Scholar

[10]

{KP04} D. R. Kowalski and A. Pelc. Polynomial deterministic rendezvous in arbitrary graphs. In Proc. of 15th ISAAC, pages 644--656, 2004.

Digital Library

Google Scholar

[11]

{Rei05}O. Reingold. Undirected ST-connectivity in log-space. In Proc. of 37th STOC, pages 376--385, 2005.

Digital Library

Google Scholar

Cited By

View all

Pelc A(2018)Use of information, memory and randomization in asynchronous gatheringJournal of Computer and System Sciences10.1016/j.jcss.2017.10.00594:C(193-205)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.jcss.2017.10.005
Fraigniaud PPelc A(2017)Decidability classes for mobile agents computingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.04.003109:C(117-128)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2017.04.003
Chalopin JDieudonné YLabourel APelc A(2016)Rendezvous in networks in spite of delay faultsDistributed Computing10.1007/s00446-015-0259-229:3(187-205)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s00446-015-0259-2
Show More Cited By

Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
1. Theory of computation

Recommendations

Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences

We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open by Dessmark et al. We also introduce an interesting variant of the rendezvous problem, which we ...
Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
Algorithms and Computation
Abstract
We study the explicit deterministic treasure hunt problem in an n-vertex network. This problem was firstly introduced by Ta-Shma, and Zwick in [9] [SODA’07]. It is the variant of the well known rendezvous problem in which one of the robot (the ...
Faster treasure hunt and better strongly universal exploration sequences
ISAAC'07: Proceedings of the 18th international conference on Algorithms and computation

We study the explicit deterministic treasure hunt problem in an n-vertex network. This problem was firstly introduced by Ta-Shma, and Zwick in [9] [SODA'07]. It is the variant of the well known rendezvous problem in which one of the robot (the treasure) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
240
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pelc A(2018)Use of information, memory and randomization in asynchronous gatheringJournal of Computer and System Sciences10.1016/j.jcss.2017.10.00594:C(193-205)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.jcss.2017.10.005
Fraigniaud PPelc A(2017)Decidability classes for mobile agents computingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.04.003109:C(117-128)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2017.04.003
Chalopin JDieudonné YLabourel APelc A(2016)Rendezvous in networks in spite of delay faultsDistributed Computing10.1007/s00446-015-0259-229:3(187-205)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s00446-015-0259-2
Dieudonné YPelc A(2015)Deterministic polynomial approach in the planeDistributed Computing10.1007/s00446-014-0216-528:2(111-129)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00446-014-0216-5
Elouasbi SPelc A(2015)Deterministic Rendezvous with Detection Using BeepsRevised Selected Papers of the 11th International Symposium on Algorithms for Sensor Systems - Volume 953610.1007/978-3-319-28472-9_7(85-97)Online publication date: 17-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-28472-9_7
Dieudonné YPelc APeleg D(2014)Gathering Despite MischiefACM Transactions on Algorithms10.1145/262965611:1(1-28)Online publication date: 11-Aug-2014
https://dl.acm.org/doi/10.1145/2629656
Miller APelc AHalldórsson MDolev S(2014)Time versus cost tradeoffs for deterministic rendezvous in networksProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611473(282-290)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611473
Dieudonné YPelc A(2014)Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic ReportsACM Transactions on Algorithms10.1145/259458111:2(1-29)Online publication date: 30-Oct-2014
https://dl.acm.org/doi/10.1145/2594581
Czyzowicz JKosowski APelc A(2014)Time versus space trade-offs for rendezvous in treesDistributed Computing10.1007/s00446-013-0201-427:2(95-109)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1007/s00446-013-0201-4
Dereniowski DPelc A(2014)Leader election for anonymous asynchronous agents in arbitrary networksDistributed Computing10.1007/s00446-013-0196-x27:1(21-38)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s00446-013-0196-x
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences

Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

Faster treasure hunt and better strongly universal exploration sequences