Polylogarithmic-overhead piecemeal graph exploration

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polylogarithmic-overhead piecemeal graph exploration

Full text

Pdf (777 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the eleventh annual conference on Computational learning theory table of contents

Madison, Wisconsin, United States

Pages: 280 - 286

Year of Publication: 1998

ISBN:1-58113-057-0

Authors

Baruch Awerbuch	Johns Hopkins University, Baltimore, MD and MIT Lab. for Computer Science
Stephen G. Kobourov	Dept. of Computer Science, Johns Hopkins University, Baltimore, MD

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 49, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/279943.279998 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	Susanne Albers , Monika R. Henzinger, Exploring unknown environments, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.416-425, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258630]
	2	Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Near-linear cost constructions of neighborhood covers in sequential and distributed environments and their applications. In $Jth Symposium on Foundations of Computer Science, pages 638-647, November 1993.
	3	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]
	4	Eldad Bar-Eli , Piotr Berman , Amos Fiat , Peiyuan Yan, Online navigation in a room, Journal of Algorithms, v.17 n.3, p.319-341, Nov. 1994
	5	M. Bender and D. Slonim. The power of team exploration: Two robots can learn unlabeled directed graphs. In 35th Symposium on Foundations of Computer Science, pages 75-87, November 1994.
	6	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
	7	Margrit Betke , Ronald L. Rivest , Mona Singh, Piecemeal Learning of an Unknown Environment, Machine Learning, v.18 n.2-3, p.231-254, Feb./March 1995 [doi>10.1007/BF00993411]
	8	M. Betke, ALGORITHMS FOR EXPLORING AN UNKNOWN GRAPH, Massachusetts Institute of Technology, Cambridge, MA, 1992
	9	Avrim Blum and P. Chalasani. An online algorithm for improving performance in navigation. In 3Jth Symposium on Foundations of Computer Science, pages 2-11, Nov 1994.
	10	Avrim Blum , Prabhakar Raghavan , Baruch Schieber, Navigating in Unfamiliar Geometric Terrain, SIAM Journal on Computing, v.26 n.1, p.110-137, Feb. 1997 [doi>10.1137/S0097539791194931]
	11	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	12	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]
	13	Xiaotie Deng and Christos H.Papadimitriou. Exploring an unknown graph. In 31st Symposium on Foundations of Computer Science, vol.1, pages 355 361, October 1990.
	14	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
	15	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]
	16	Nagewara S. V. Rao, Srikumar Kareti, Weimin Shi, and S. Sitharama Iyengm'. Robot navigation in unknown terrains: Introductory survey of nonheuristic algorithms. Technical report, Oak Pddge National Laboratory, July 1993. ORNL/TM- 12410.

CITED BY 3

	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
	Leszek Gąsieniec , Ralf Klasing , Russell Martin , Alfredo Navarra , Xiaohui Zhang, Fast periodic graph exploration with constant memory, Journal of Computer and System Sciences, v.74 n.5, p.808-822, August, 2008
	Christian A. Duncan , Stephen G. Kobourov , V. S. Anil Kumar, Optimal constrained graph exploration, ACM Transactions on Algorithms (TALG), v.2 n.3, p.380-402, July 2006