Exploring unknown environments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Exploring unknown environments

Full text

Pdf (1.33 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 416 - 425

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Susanne Albers	Max-Planck-Institut für Informatik, Im Stadtwald, 66123, Saarbrücken, Germany
Monika R. Henzinger	Systems Research Center, Digital Equipment Corporation, 130 Lytton Ave., Palo Alto, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 34, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258630 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Baruch Awerbuch , Margrit Betke , Ronald L. Rivest , Mona Singh, Piecemeal graph exploration by a mobile robot (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.321-328, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225337]
	2	E. Bar-Eli , Piotr Berman , A. Fiat , Peiyuan Yan, On-line navigation in a room, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.237-249, September 1992, Orlando, Florida, United States
	3	Piotr Berman , Avrim Blum , Amos Fiat , Howard Karloff , Adi Rosén , Michael Saks, Randomized robot navigation algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.75-84, January 28-30, 1996, Atlanta, Georgia, United States
	4	A. Blum and P. Chalasani. An on-line algorithm for improving performance in navigation. Proc. 34th Syrup. on Foundations of Computer Science, o-11, 1994.
	5	Avrim Blum , Prabhakar Raghavan , Baruch Schieber, Navigating in unfamiliar geometric terrain, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.494-504, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103419]
	6	Margrit Betke , Ronald L. Rivest , Mona Singh, Piecemeal learning of an unknown environment, Proceedings of the sixth annual conference on Computational learning theory, p.277-286, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168352]
	7	M. Bender and D. Slonim. The power of teach exploration' two robots can learn unlabeled directed graphs. Proc. 35th Syrup. on Foundations of Computer Science, 75-85, 1994.
	8	Xiaotie Deng , Tiko Kameda , Christos Papadimitriou, How to learn an unknown environment (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.298-303, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185382]
	9	X. Deng and C. H. Papadimitriou. Exploring an unknown graph. Proc. 31st Syrup. on Foundations of Computer Science. 356-361. 1990.
	10	X. Deng and C. H. Papadimitriou. Exploring an unknown graph. Revised version of {9}.
	11	Frank Hoffmann , Christian Icking , Rolf Klein , Klaus Kriegel, A competitive strategy for learning a polygon, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.166-174, January 05-07, 1997, New Orleans, Louisiana, United States
	12	E. Koutsoupias. Result reported in {10}.
	13	Christos H. Papadimitriou , Mihalis Yannakakis, Shortest paths without a map, Theoretical Computer Science, v.84 n.1, p.127-150, July 22, 1991 [doi>10.1016/0304-3975(91)90263-2]
	14	R. Rivest. Problem formulation cited in {9}.

CITED BY 11

	Gianluca De Marco , Andrzej Pelc, Deterministic broadcasting time with partial knowledge of the network, Theoretical Computer Science, v.290 n.3, p.2009-2020, 3 January 2003
	Baruch Awerbuch , Stephen G. Kobourov, Polylogarithmic-overhead piecemeal graph exploration, Proceedings of the eleventh annual conference on Computational learning theory, p.280-286, July 24-26, 1998, Madison, Wisconsin, United States
	Michael A. Bender , Antonio Fernández , Dana Ron , Amit Sahai , Salil Vadhan, The power of a pebble: exploring and mapping directed graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.269-278, May 24-26, 1998, Dallas, Texas, United States
	Pierre Fraigniaud , Andrzej Pelc , David Peleg , Stéphane Pérennes, Assigning labels in unknown anonymous networks (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.101-111, July 16-19, 2000, Portland, Oregon, United States
	Christian A. Duncan , Stephen G. Kobourov , V. S. Anil Kumar, Optimal constrained graph exploration, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.807-814, January 07-09, 2001, Washington, D.C., United States
	Petrişor Panaite , Andrzej Pelc, Exploring unknown undirected graphs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.316-322, January 25-27, 1998, San Francisco, California, United States
	Michael A. Bender , Antonio Fernández , Dana Ron , Amit Sahai , Salil Vadhan, The power of a pebble: exploring and mapping directed graphs, Information and Computation, v.176 n.1, p.1-21, July 2002
	Lali Barrière , Paola Flocchin , Pierre Fraigniau , Nicola Santor, Can we elect if we cannot compare?, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Esther M. Arkin , Michael A. Bender , Dongdong Ge, Improved approximation algorithms for the freeze-tag problem, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Vida Dujmoviác , Sue Whitesides, On validating planar worlds, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.791-792, January 07-09, 2001, Washington, D.C., United States
	Anders Dessmark , Andrzej Pelc, Distributed Colouring and Communication in Rings with Local Knowledge, Combinatorics, Probability and Computing, v.13 n.2, p.123-136, March 2004