Memory Efficient Anonymous Graph Exploration | SpringerLink
Skip to main content
Springer Nature Link
Log in

Memory Efficient Anonymous Graph Exploration

  • Conference paper
Graph-Theoretic Concepts in Computer Science (WG 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5344))

Included in the following conference series:

Abstract

Efficient exploration of unknown or unmapped environments has become one of the fundamental problem domains in algorithm design. Its applications range from robot navigation in hazardous environments to rigorous searching, indexing and analysing digital data available on the Internet. A large number of exploration algorithms has been proposed under various assumptions about the capability of mobile (exploring) entities and various characteristics of the environment which are to be explored. This paper considers the graph model, where the environment is represented by a graph of connections in which discrete moves are permitted only along its edges. Designing efficient exploration algorithms in this model has been extensively studied under a diverse set of assumptions, e.g., directed vs undirected graphs, anonymous nodes vs nodes with distinct identities, deterministic vs probabilistic solutions, single vs multiple agent exploration, as well as in the context of different complexity measures including the time complexity, the memory consumption, and the use of other computational resources such as tokens and messages. In this work the emphasis is on memory efficient exploration of anonymous graphs. We discuss in more detail three approaches: random walk, Propp machine and basic walk, reviewing major relevant results, presenting recent developments, and commenting on directions for further research.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM Journal on Computing 29, 1164–1188 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aldous, D.J.: On the time taken by random walks on finite groups to visit every state. Journal Probability Theory and Related Fields 62(3), 361–374 (1983)

    MathSciNet  MATH  Google Scholar 

  3. Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: FOCS 1979, pp. 218–223 (1979)

    Google Scholar 

  4. Alon, N., Azar, Y., Ravid, Y.: Universal sequences for complete graphs. Discrete Appl. Math. 27(1-2), 25–28 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  5. Alon, N., Avin, C., Koucky, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. In: SPAA 2008: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pp. 119–128. ACM, New York (2008)

    Chapter  Google Scholar 

  6. Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Information and Computation 152(2), 155–172 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bar-Noy, A., Borodin, A., Karchmer, M., Linial, N., Werman, M.: Bounds on universal sequences. SIAM J. Comput. 18, 268–277 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bender, M., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. Information and Computation 176(1), 1–21 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bender, M., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Proc. of FOCS 1994, pp. 75–85 (1994)

    Google Scholar 

  10. Bhatt, S., Even, S., Greenberg, D., Tayar, R.: Traversing Directed Eulerian Mazes. Journal of Graph Algorithms and Applications 6(2), 157–173 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  11. Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM Journal on Computing 26, 110–137 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  12. Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Proc. of FOCS 1978, pp. 132–142 (1978)

    Google Scholar 

  13. Bridgland, M.F.: Universal traversal sequences for paths and cycles. J. Algorithms 8(5), 395–404 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  14. Broder, A.Z., Karlin, A.R., Raghavan, P., Upfal, E.: Trading space for time in undirected s-t connectivity. SIAM J. Comput. 23(2), 324–334 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  15. Budach, L.: Automata and labyrinths. Math. Nachrichten, 195–282 (1978)

    Google Scholar 

  16. Buss, J.F., Tompa, M.: Lower bounds on universal traversal sequences based on chains of length five. Inf. Comput. 120(2), 326–329 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  17. Chandra, A.K., Raghavan, P., Ruzzo, W.L., Smolensky, R.: The electrical resistance of a graph captures its commute and cover times. In: Proc. STOC 1989: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 574–586. ACM Press, New York (1989)

    Chapter  Google Scholar 

  18. Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), pp. 335–346 (2005)

    Google Scholar 

  19. Cook, S.A., Rackoff, C.: Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing 9(3), 636–652 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  20. Cooper, C., Frieze, A.: The cover time of random regular graphs. SIAM J. Discret. Math. 18(4), 728–740 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  21. Cooper, C., Frieze, A.M.: Crawling on web graphs. In: Proc. STOC 2002, pp. 419–427 (2002)

    Google Scholar 

  22. Cooper, C., Frieze, A.M., Radzik, T.: Multiple random walks in random regular graphs (unpublished manuscript, 2008)

    Google Scholar 

  23. Cooper, C., Klasing, R., Radzik, T.: A randomized algorithm for the joining protocol in dynamic distributed networks. Technical Report RR-1432-07, LaBRI, Bordeaux, France (June 2007)

    Google Scholar 

  24. Cooper, J.N., Spencer, J.: Simulating a random walk with constant error. Combinatorics, Probability and Computing 15, 815–822 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  25. Cooper, J., Doerr, B., Friedrich, T., Spencer, J.H.: Deterministic random walks on regular trees. In: Proc. of SODA 2008, pp. 766–772 (2008)

    Google Scholar 

  26. Cooper, J., Doerr, B., Spencer, J.H., Tardos, G.: Deterministic random walks on the integers. European Journal of Combinatorics 28(8), 2072–2090 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  27. Czyzowicz, J., Dobrev, S., Gąsieniec, L., Ilcinkas, D., Jansson, J., Klasing, R., Lignos, I., Martin, R., Sadakane, K., Sung, W.-K.: More efficient periodic traversal in anonymous undirected graphs (unpublished manuscript, 2008)

    Google Scholar 

  28. Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environment: The rectilinear case. Journal of the ACM 45, 215–245 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  29. Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. Journal of Graph Theory 32(3), 265–297 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  30. Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. Theoretical Computer Science 326(1-3), 343–362 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  31. Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. Journal of Algorithms 51, 38–63 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  32. Dobrev, S., Jansson, J., Sadakane, K., Sung, W.-K.: Finding Short Right-Hand-on-the-Wall Walks in Graphs. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 127–139. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  33. Doerr, B., Friedrich, T.: Deterministic Random Walks on the Two-Dimensional Grid. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 474–483. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  34. Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. ACM Transaction on Algorithms 2(3), 380–402 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  35. Feige, U.: A tight upper bound on the cover time for random walks on graphs. Random Structures and Algorithms 6(1), 51–54 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  36. Feige, U.: A tight lower bound on the cover time for random walks on graphs. Random Struct. Algorithms 6(4), 433–438 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  37. Feige, U.: Collecting coupons on trees, and the cover time of random walks. Computational Complexity 6(4), 341–356 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  38. Flocchini, P., Mans, B., Santoro, N.: On the impact of sense of direction on message complexity. Information Processing Letters 63(1), 23–31 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  39. Flocchini, P., Mans, B., Santoro, N.: Sense of direction: definition, properties and classes. Networks 32(3), 165–180 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  40. Fraigniaud, P., Gavoille, C., Mans, B.: Interval routing schemes allow broadcasting with linear message-complexity. Distributed Computing 14(4), 217–229 (2001)

    Article  MATH  Google Scholar 

  41. Fraigniaud, P., Ilcinkas, D.: Digraph exploration with little memory. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 246–257. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  42. Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theoretical Computer Science 345(2-3), 331–344 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  43. Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar hamiltonian circuit problem is np-complete. SIAM J. Comput. 5(4), 704–714 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  44. Gąsieniec, L., Klasing, R., Martin, R., Navarra, A., Zhang, X.: Fast Periodic Graph Exploration with Constant Memory. J. Comput. Syst. Sci. 74(5), 808–822 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  45. Gąsieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: SODA, pp. 585–594 (2007)

    Google Scholar 

  46. Hoory, S., Wigderson, A.: Universal traversal sequences for expander graphs. Inf. Process. Lett. 46(2), 67–69 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  47. Ikeda, S., Kubo, I., Okumoto, N., Yamashita, M.: Impact of local topological information on random walks on finite graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1054–1067. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  48. Ilcinkas, D.: Setting Port Numbers for Fast Graph Exploration. In: Flocchini, P., Gąsieniec, L. (eds.) SIROCCO 2006. LNCS, vol. 4056, pp. 59–69. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  49. Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: Proc. STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 356–364. ACM Press, New York (1994)

    Chapter  Google Scholar 

  50. Istrail, S.: Polynomial universal traversing sequences for cycles are constructible. In: Proc. STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 491–503. ACM Press, New York (1988)

    Chapter  Google Scholar 

  51. Karloff, H.J., Paturi, R., Simon, J.: Universal traversal sequences of length n O(logn) for cliques. Inf. Process. Lett. 28(5), 241–243 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  52. Koucký, M.: Universal traversal sequences with backtracking. J. Comput. Syst. Sci. 65(4), 717–726 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  53. Koucký, M.: Log-space constructible universal traversal sequences for cycles of length o(n4.03). Theor. Comput. Sci. 296(1), 117–144 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  54. Kozen, D.: Automata and planar graphs. In: Proc. of Fundations Computatial Theory (FCT 1979), pp. 243–254 (1979)

    Google Scholar 

  55. Law, C., Siu, K.-Y.: Distributed construction of random expander graphs. In: Proc. 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (April 2003)

    Google Scholar 

  56. Panaite, P., Pelc, A.: Impact of topographic information on graph exploration efficiency. Networks 36, 96–103 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  57. Priezzhev, V.B., Dhar, D., Dhar, A., Krishnamurthy, S.: Eulerian walkers as a model of selforganized criticality. Physics Review Letters 77, 5079–5082 (1996)

    Article  Google Scholar 

  58. Rabin, M.O.: Maze threading automata. Technical Report Seminar Talk, University of California at Berkeley (October 1967)

    Google Scholar 

  59. Rao, N., Kareti, S., Shi, W., Iyengar, S.: Robot navigation in unknown terrains: Introductory survey of length, non-heuristic algorithms. Technical Report ORNL/TM12410, Oak Ridge National Lab (1993)

    Google Scholar 

  60. Reingold, O.: Undirected st-connectivity in log-space. In: Proc. STOC 2005, pp. 376–385 (2005)

    Google Scholar 

  61. Rollik, H.A.: Automaten in planaren graphen. Acta Informatica 13, 287–298 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  62. Rubinfeld, R.: The cover time of a regular expander is O(n log n). Information Processing Letters 35, 49–51 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  63. Winkler, P., Zuckerman, D.: Multiple cover time. Random Structures and Algorithms 9, 403–411 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  64. Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A Distributed Ant Algorithm for Efficiently Patrolling a Network. Algorithmica 37, 165–186 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  65. Zuckerman, D.: A technique for lower bounding the cover time. SIAM J. Discret. Math. 5(1), 81–87 (1992)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Liverpool, Liverpool, L69 3BX, United Kingdom

    Leszek Gąsieniec

  2. Department of Computer Science, King’s College London, Strand, London, WC2R 2LS, United Kingdom

    Tomasz Radzik

Authors
  1. Leszek Gąsieniec
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tomasz Radzik
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Durham University, South Road, DH1 3LE, Durham, UK

    Hajo Broersma , Tom Friedetzky  & Daniel Paulusma ,  & 

  2. Department of Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK

    Thomas Erlebach

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gąsieniec, L., Radzik, T. (2008). Memory Efficient Anonymous Graph Exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2008. Lecture Notes in Computer Science, vol 5344. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92248-3_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92248-3_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-92247-6

  • Online ISBN: 978-3-540-92248-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation