Map construction of unknown graphs by multiple agents. (English) Zbl 1124.68078
Summary: We consider a distributed version of the graph exploration and mapping problem where a mobile agent has to traverse the edges of an unlabelled (i.e., anonymous) graph and return to its starting point, building a map of the graph in the process. In our case, instead of a single agent, there are \(k\) identical (i.e., mutually indistinguishable) agents initially dispersed among the \(n\) nodes of the graph. The agents can communicate by writing to the small public bulletin boards available at each node. The objective is for each agent to build an identically labelled map of the graph; we call this the Labelled Map Construction problem. This problem is much more difficult than exploration by a single agent, because it involves achieving cooperation among multiple agents. In fact, this problem is deterministically unsolvable in some cases. We present deterministic algorithms that successfully and efficiently solve the problem under the condition that the values of \(n\) and \(k\) are co-prime with each other. We also show how the problem of Labelled Map Construction is related to other problems like leader election and rendezvous of agents.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
labelled map construction; graph exploration; leader election; rendezvous; anonymous mobile agentsReferences:
| [1] | Afek, Y.; Gafni, E., Distributed algorithms for unidirectional networks, SIAM Journal on Computing, 23, 6, 1152-1178 (1994) · Zbl 0834.68039 |
| [2] | Albers, S.; Henzinger, M. R., Exploring unknown environments, SIAM Journal on Computing, 29, 1164-1188 (2000) · Zbl 0947.68165 |
| [3] | Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous (2003), Kluwer · Zbl 1034.91017 |
| [4] | D. Angluin, Local and global properties in networks of processors, in: Proc. of 12th Symposium on Theory of Computing, STOC’80, 1980, pp. 82-93; D. Angluin, Local and global properties in networks of processors, in: Proc. of 12th Symposium on Theory of Computing, STOC’80, 1980, pp. 82-93 |
| [5] | Averbakh, I.; Berman, O., \((p - l) /(p + 1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective, Discrete Applied Mathematics, 75, 201-216 (1997) · Zbl 0879.68077 |
| [6] | L. Barrière, P. Flocchini, P. Fraigniaud, N. Santoro, Can we elect if we cannot compare? in: Proc. 15th ACM Symp. on Parallel Algorithms and Architectures, SPAA’03, 2003, pp. 200-209; L. Barrière, P. Flocchini, P. Fraigniaud, N. Santoro, Can we elect if we cannot compare? in: Proc. 15th ACM Symp. on Parallel Algorithms and Architectures, SPAA’03, 2003, pp. 200-209 |
| [7] | Barrière, L.; Flocchini, P.; Fraigniaud, P.; Santoro, N., Rendezvous and election of mobile agents: impact of sense of direction, Theory of Computing Systems, 40, 2, 143-162 (2007), Preliminary version in Proc. 10th Coll. on Structural Information and Communication complexity, SIROCCO’03, 2003, pp. 17-32 · Zbl 1107.68022 |
| [8] | M. Bender, A. Fernandez, D. Ron, A. Sahai, S. Vadhan, The power of a pebble: Exploring and mapping directed graphs, in: Proc. 30th ACM Symp. on Theory of Computing, STOC’98, 1998, pp. 269-287; M. Bender, A. Fernandez, D. Ron, A. Sahai, S. Vadhan, The power of a pebble: Exploring and mapping directed graphs, in: Proc. 30th ACM Symp. on Theory of Computing, STOC’98, 1998, pp. 269-287 · Zbl 1027.68652 |
| [9] | M. Bender, D.K. Slonim, The power of team exploration: Two robots can learn unlabeled directed graphs, in: Proc. 35th Symp. on Foundations of Computer Science, FOCS’94, 1994, pp. 75-85; M. Bender, D.K. Slonim, The power of team exploration: Two robots can learn unlabeled directed graphs, in: Proc. 35th Symp. on Foundations of Computer Science, FOCS’94, 1994, pp. 75-85 |
| [10] | P. Boldi, S. Vigna, An effective characterization of computability in anonymous networks, in: Proc. of 15th Int. Conference on Distributed Computing, DISC’01, 2001, pp. 33-47; P. Boldi, S. Vigna, An effective characterization of computability in anonymous networks, in: Proc. of 15th Int. Conference on Distributed Computing, DISC’01, 2001, pp. 33-47 · Zbl 1024.68508 |
| [11] | Burns, J. E.; Pachl, J., Uniform self-stabilizing rings, ACM Transactions on Programming Languages and Systems, 11, 2, 330-344 (1989) |
| [12] | S. Das, P. Flocchini, A. Nayak, N. Santoro, Distributed exploration of an unknown graph, in: Proc. 12th Coll. on Structural Information and Communication Complexity, SIROCCO’05, 2005, pp. 99-114; S. Das, P. Flocchini, A. Nayak, N. Santoro, Distributed exploration of an unknown graph, in: Proc. 12th Coll. on Structural Information and Communication Complexity, SIROCCO’05, 2005, pp. 99-114 · Zbl 1085.68599 |
| [13] | Deng, X.; Papadimitriou, C. H., Exploring an unknown graph, Journal of Graph Theory, 32, 3, 265-297 (1999) · Zbl 0941.68099 |
| [14] | A. Dessmark, P. Fraigniaud, A. Pelc, Deterministic rendezvous in graphs, in: Proc. 11th European Symposium on Algorithms, ESA’03, 2003, pp. 184-195; A. Dessmark, P. Fraigniaud, A. Pelc, Deterministic rendezvous in graphs, in: Proc. 11th European Symposium on Algorithms, ESA’03, 2003, pp. 184-195 · Zbl 1266.68143 |
| [15] | Dessmark, A.; Pelc, A., Optimal graph exploration without good maps, Theoretical Computer Science, 326, 1-3, 343-362 (2004) · Zbl 1071.68081 |
| [16] | Diks, K.; Fraigniaud, P.; Kranakis, E.; Pelc, A., Tree exploration with little memory, Journal of Algorithms, 51, 38-63 (2004) · Zbl 1067.68100 |
| [17] | Dudek, G.; Jenkin, M.; Milios, E.; Wilkes, D., Robotic exploration as graph construction, Transactions on Robotics and Automation, 7, 6, 859-865 (1991) |
| [18] | P. Flocchini, E. Kranakis, D. Krizanc, N. Santoro, C. Sawchuk, Multiple mobile agent rendezvous in a ring, in: Proc. 6th Latin American Theoretical Informatics Symposium, LATIN’04, 2004, pp. 599-608; P. Flocchini, E. Kranakis, D. Krizanc, N. Santoro, C. Sawchuk, Multiple mobile agent rendezvous in a ring, in: Proc. 6th Latin American Theoretical Informatics Symposium, LATIN’04, 2004, pp. 599-608 · Zbl 1196.68021 |
| [19] | P. Fraigniaud, L. Gasieniec, D. Kowalski, A. Pelc, Collective tree exploration, in: 6th Latin American Theoretical Informatics Symp., LATIN’04, 2004, pp. 141-151; P. Fraigniaud, L. Gasieniec, D. Kowalski, A. Pelc, Collective tree exploration, in: 6th Latin American Theoretical Informatics Symp., LATIN’04, 2004, pp. 141-151 · Zbl 1196.68171 |
| [20] | P. Fraigniaud, D. Ilcinkas, Digraph exploration with little memory, in: 21st Symp. on Theoretical Aspects of Computer Science, STACS’04, 2004, pp. 246-257; P. Fraigniaud, D. Ilcinkas, Digraph exploration with little memory, in: 21st Symp. on Theoretical Aspects of Computer Science, STACS’04, 2004, pp. 246-257 · Zbl 1122.68676 |
| [21] | Frederickson, G. N.; Hecht, M. S.; Kim, C. E., Approximation algorithms for some routing problems, SIAM Journal on Computing, 7, 178-193 (1978) |
| [22] | Gallager, R. G.; Humblet, P. A.; Spira, P. M., A distributed algorithm for minimum-weight spanning trees, ACM Transactions on Programming Languages and Systems, 5, 1, 66-77 (1983) · Zbl 0498.68040 |
| [23] | L. Gasieniec, A. Pelc, T. Radzik, X. Zhang, Tree exploration with logarithmic memory, in: 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 07, 2007; L. Gasieniec, A. Pelc, T. Radzik, X. Zhang, Tree exploration with logarithmic memory, in: 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 07, 2007 · Zbl 1302.68216 |
| [24] | Korach, E.; Kutten, S.; Moran, S., A modular technique for the design of efficient distributed leader finding algorithms, ACM Transactions on Programming Languages and Systems, 12, 1, 84-101 (1990) |
| [25] | E. Kranakis, D. Krizanc, N. Santoro, C. Sawchuk, Mobile agent rendezvous in a ring, in: Int. Conf. on Distributed Computing Systems, ICDCS 03, 2003, pp. 592-599; E. Kranakis, D. Krizanc, N. Santoro, C. Sawchuk, Mobile agent rendezvous in a ring, in: Int. Conf. on Distributed Computing Systems, ICDCS 03, 2003, pp. 592-599 · Zbl 1196.68021 |
| [26] | S. Kutten, Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks or: Traversing one way streets with no map, in: Proc. of Ninth Int. Conference on Computer Communication, ICCC, 1988, pp. 446-452; S. Kutten, Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks or: Traversing one way streets with no map, in: Proc. of Ninth Int. Conference on Computer Communication, ICCC, 1988, pp. 446-452 |
| [27] | Panaite, P.; Pelc, A., Exploring unknown undirected graphs, Journal of Algorithms, 33, 281-295 (1999) · Zbl 0957.68092 |
| [28] | N. Sakamoto, Comparison of initial conditions for distributed algorithms on anonymous networks, in: Proc. of the 18th Annual ACM Symp. on Principles of Distributed Computing, PODC ’99, 1999, pp. 173-179; N. Sakamoto, Comparison of initial conditions for distributed algorithms on anonymous networks, in: Proc. of the 18th Annual ACM Symp. on Principles of Distributed Computing, PODC ’99, 1999, pp. 173-179 · Zbl 1321.68487 |
| [29] | Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1, 2, 146-160 (1972) · Zbl 0251.05107 |
| [30] | Yamashita, M.; Kameda, T., Computing on anonymous networks: Part I— Characterizing the solvable cases, IEEE Transactions on Parallel and Distributed Systems, 7, 1, 69-89 (1996) |
| [31] | X. Yu, M. Yung, Agent rendezvous: A dynamic symmetry-breaking problem, in: Int. Coll. on Automata Languages and Programming, ICALP’96, 1996, pp. 610-621; X. Yu, M. Yung, Agent rendezvous: A dynamic symmetry-breaking problem, in: Int. Coll. on Automata Languages and Programming, ICALP’96, 1996, pp. 610-621 · Zbl 1046.68535 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
