Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Edge exploration of anonymous graph by mobile agent with external help

  • Regular Paper
  • Published:
Computing Aims and scope Submit manuscript

Abstract

Exploration of an unknown network by one or multiple mobile entities is a well studied problem which has various applications like treasure hunt, collecting data from some node in the network or samples from contaminated mines. In this paper, we study the problem of edge exploration of an n node graph by a mobile agent. The nodes of the graph are anonymous, and the edges at a node of degree d are arbitrarily assigned unique port numbers in the range \(0,1, \dots , d-1\). A mobile agent, starting from a node, has to visit all the edges of the graph and stop. The time of the exploration is the number of edges the agent traverses before it stops. The task of exploration can not be performed even for a class of cycles if no additional help is provided. We consider two different ways of providing additional help to the agent by an Oracle. In the first scenario, the nodes of the graph are provided some short labels by the Oracle. In the second scenario, some additional information, called advice, is provided to the agent in the form of a binary string. For the first scenario, we show that exploration can be done by providing constant size labels to the nodes of the graph. For the second scenario, we show that exploration can not be completed within time \(o(n^{\frac{8}{3}})\) regardless of the advice provided to the agent. We propose an upper bound result by designing an \(O(n^3)\) algorithm with \(O(n \log n)\) advice. We also show a lower bound \(\Omega (n^{\frac{8}{3}})\) on the size of advice to perform exploration in \(O(n^3)\) time. In addition, we have done experimental studies on randomly created anonymous graph to analyze time complexity of exploration with \(O(n \log n)\) size advice.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Awerbuch B, Betke M, Ronald L, Rivest M. Singh (1999) Piecemeal graph exploration by a mobile robot. Inf Comput 152:155–172

    Article  MATH  Google Scholar 

  2. Bender MA, Fernández A, Ron D, Sahai A, Vadhan SP (2002) The power of a pebble: exploring and mapping directed graphs. Inf Comput 176:1–21

    Article  MATH  Google Scholar 

  3. Bender MA, Slonim D (1994) The power of team exploration: two robots can learn unlabeled directed graphs. In: Proceedings of the 35th annual symposium on foundations of computer science (FOCS 1994), pp 75–85

  4. Borodin A, Ruzzo W, Tompa M (1992) Lower bounds on the length of universal traversal sequences. J Comput Syst Sci 45:180–203

    Article  MATH  Google Scholar 

  5. Boyar J, Favrholdt LM, Kudahl C, Larsen KS, Mikkelsen JW (2017) Online algorithms with advice: a survey. ACM Comput Surv 50(2):19:1-19:34

    MATH  Google Scholar 

  6. Chalopin J, Das S, Kosowski A (2010) Constructing a map of an anonymous graph: applications of universal sequences. In: Proceedings of the 14th international conference on principles of distributed systems (OPODIS 2010), pp 119–134

  7. Cohen R, Fraigniaud P, Ilcinkas D, Korman A, Peleg D (2008) Label-guided graph exploration by a finite automaton. ACM Trans Algorithms

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

    Article  MATH  Google Scholar 

  9. Dobrev S, Kralovic R, Markou E (2012) Online graph exploration with advice. In: Proceedings of the 19th international colloquium on structural information and communication complexity (SIROCCO 2012), pp 267–278

  10. Duncan CA, Kobourov SG, Anil Kumar VS (2006) Optimal constrained graph exploration. ACM Trans Algorithms 2:380–402

    Article  MATH  Google Scholar 

  11. Ellen F, Gorain B, Miller A, Pelc A (2019) Constant-length labeling schemes for deterministic radio broadcast. In: Proceedings of the 31st ACM symposium on parallelism in algorithms and architectures (SPAA) 2019, pp 171–178

  12. Emek Y, Fraigniaud P, Korman A, Rosen A (2011) Online computation with advice. Theoret Comput Sci 412:2642–2656

    Article  MATH  Google Scholar 

  13. Fraigniaud P, Gavoille C, Ilcinkas D, Pelc A (2009) Distributed computing with advice: Information sensitivity of graph coloring. Distrib Comput 21:395–403

    Article  MATH  Google Scholar 

  14. Fraigniaud P, Ilcinkas D, Pelc A (2010) Communication algorithms with advice. J Comput Syst Sci 76:222–232

  15. Fraigniaud P, Ilcinkas D, Pelc A (2008) Tree exploration with advice. Inf Comput 206:1276–1287

    Article  MATH  Google Scholar 

  16. Fraigniaud P, Korman A, Lebhar E (2010) Local MST computation with short advice. Theory Comput Syst 47:920–933

    Article  MATH  Google Scholar 

  17. Fraigniaud P, Ilcinkas D (2004) Directed graphs exploration with little memory. In: Proceedings of the 21st symposium on theoretical aspects of computer science (STACS 2004), pp 246–257

  18. Fusco E, Pelc A (2011) Trade-offs between the size of advice and broadcasting time in trees. Algorithmica 60:719–734

    Article  MATH  Google Scholar 

  19. Fusco E, Pelc A, Petreschi R (2016) Topology recognition with advice. Inf Comput 247:254–265

    Article  MATH  Google Scholar 

  20. Gavoille C, Peleg D, Pérennes S, Raz R (2004) Distance labeling in graphs. J Algorithms 53:85–112

    Article  MATH  Google Scholar 

  21. Gorain B, Pelc A (2018) Deterministic graph exploration with advice. ACM Trans Algorithms 15:8:1-8:17

    MATH  Google Scholar 

  22. Gorain B, Pelc A (2021) Short labeling schemes for topology recognition in wireless tree networks. Theor Comput Sci 861:23–44

    Article  MATH  Google Scholar 

  23. Gorain B, Pelc A (2021) Finding the size and the diameter of a radio network using short labels. Theor Comput Sci 864:20–33

    Article  MATH  Google Scholar 

  24. Ilcinkas D, Kowalski D, Pelc A (2012) Fast radio broadcasting with advice. Theor Comput Sci 411:1544–1557

    Article  MATH  Google Scholar 

  25. Korman A, Kutten S, Peleg D (2010) Proof labeling schemes. Distrib Comput 22:215–233

    Article  MATH  Google Scholar 

  26. Megow N, Mehlhorn K, Schweitzer P (2012) Online graph exploration: new results on old and new algorithms. Theoret Comput Sci 463:62–72

    Article  MATH  Google Scholar 

  27. Nisse N, Soguet D (2009) Graph searching with advice. Theor Comput Sci 410:1307–1318

    Article  MATH  Google Scholar 

  28. Pelc A, Tiane A (2014) Efficient grid exploration with a stationary token. Int J Found Comput Sci 25:247–262

    Article  MATH  Google Scholar 

  29. Rao NSV, Kareti S, Shi W, Iyengar SS (1993) Robot navigation in unknown terrains: introductory survey of non-heuristic algorithms. Technical report ORNL/TM-12410, Oak Ridge National Laboratory

  30. Reingold O (2008) Undirected connectivity in log-space. J ACM 55:1–24

    Article  MATH  Google Scholar 

Download references

Acknowledgements

Barun Gorain and Kaushik Mondal acknowledge the support of the Science and Engineering Research Board (SERB), Department of Science and Technology, Govt. of India (Grant Number: CRG/2020/005964). Amit K. Dhar, Barun Gorain, and Rishi Ranjan Singh acknowledges the support of the Research Initiation Grant supported by IIT Bhilai, India. Barun Gorain also acknowledges partial support of SERB (Grant Number: MTR/2021/000118). Kaushik Mondal also acknowledges the support of FIST program, supported by Department of Science and Technology, Govt. of India (SR/FST/MS-I/2018/22(C)).

Author information

Author notes

  1. Amit Kumar Dhar, Kaushik Mondal, Shaswati Patra and Rishi Ranjan Singh have contributed equally to this work.

Authors and Affiliations

  1. Department of Electrical Engineering and Computer Science, Indian Institute of Technology Bhilai, Raipur, India

    Amit Kumar Dhar, Barun Gorain, Shaswati Patra & Rishi Ranjan Singh

  2. Department of Mathematics, Indian Institute of Technology Ropar, Rupnagar, India

    Kaushik Mondal

Authors
  1. Amit Kumar Dhar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Barun Gorain
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kaushik Mondal
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shaswati Patra
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Rishi Ranjan Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Barun Gorain.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this paper appears in Proc. 13th International Conference on Combinatorial Optimization and Applications (COCOA’19).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dhar, A.K., Gorain, B., Mondal, K. et al. Edge exploration of anonymous graph by mobile agent with external help. Computing 105, 483–506 (2023). https://doi.org/10.1007/s00607-022-01136-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-022-01136-8

Keywords

Mathematics Subject Classification

Search

Navigation