{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T15:11:38Z","timestamp":1787238698405,"version":"build-2736575974"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T00:00:00Z","timestamp":1414627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Chair in Distributed Computing at the Universit\u00e9 du Qu\u00e9bec en Outaouais"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,11,17]]},"abstract":"<jats:p>\n                    A team consisting of an unknown number of mobile agents starting from different nodes of an unknown network, possibly at different times, have to explore the network: Every node must be visited by at least one agent, and all agents must eventually stop. Agents are anonymous (identical), execute the same deterministic algorithm, and move in synchronous rounds along links of the network. They are silent: They cannot send any messages to other agents or mark visited nodes in any way. In the absence of any additional information, exploration with termination of an arbitrary network in this model, devoid of any means of communication between agents, is impossible. Our aim is to solve the exploration problem by giving to agents very restricted\n                    <jats:italic>local traffic reports<\/jats:italic>\n                    . Specifically, an agent that is at a node\n                    <jats:italic>v<\/jats:italic>\n                    in a given round is provided with three bits of information answering the following questions: Am I alone at\n                    <jats:italic>v<\/jats:italic>\n                    ? Did any agent enter\n                    <jats:italic>v<\/jats:italic>\n                    in this round? Did any agent exit\n                    <jats:italic>v<\/jats:italic>\n                    in this round? We show that this small amount of information permits us to solve the exploration problem in arbitrary networks. More precisely, we give a deterministic terminating exploration algorithm working in arbitrary networks for all initial configurations that are not\n                    <jats:italic>perfectly symmetric<\/jats:italic>\n                    ; that is, in which there are agents with different\n                    <jats:italic>views<\/jats:italic>\n                    of the network. The algorithm works in polynomial time in the (unknown) size of the network. A deterministic terminating exploration algorithm working for all initial configurations in arbitrary networks does not exist.\n                  <\/jats:p>","DOI":"10.1145\/2594581","type":"journal-article","created":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T15:28:54Z","timestamp":1414769334000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports"],"prefix":"10.1145","volume":"11","author":[{"given":"Yoann","family":"Dieudonn\u00e9","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Picardie Jules Verne, Amiens, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732428X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921663"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00054-U"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)89161-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/225298.225337"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276759"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365703"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993411"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS'10)","author":"Chalopin J.","unstructured":"J. Chalopin , S. Das , and A. Kosowski . 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'10) , 119--134. J. Chalopin, S. Das, and A. Kosowski. 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'10), 119--134."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG'10)","author":"Chalopin J.","unstructured":"J. Chalopin , P. Flocchini , B. Mans , and N. Santoro . 2010. Network exploration by silent and oblivious robots . In Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG'10) . 208--219. J. Chalopin, P. Flocchini, B. Mans, and N. Santoro. 2010. Network exploration by silent and oblivious robots. In Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG'10). 208--219."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0141-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199911)32:3%26lt;%26gt;1.0.CO;2-F"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.031"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1953563.1953571"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11476-2_16"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01)","author":"Duncan C. A.","year":"2001","unstructured":"C. A. Duncan , S. G. Kobourov , and V. S. A. Kumar . 2001 . Optimal constrained graph exploration . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01) . 807--814. C. A. Duncan, S. G. Kobourov, and V. S. A. Kumar. 2001. Optimal constrained graph exploration. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01). 807--814."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.007"},{"issue":"2013","key":"e_1_2_1_21_1","first-page":"562","article-title":"Computing without communicating: Ring exploration by asynchronous oblivious robots","volume":"65","author":"Flocchini P.","year":"2007","unstructured":"P. Flocchini , D. Ilcinkas , A. Pelc , and N. Santoro . 2007 . Computing without communicating: Ring exploration by asynchronous oblivious robots . Algorithmica 65 ( 2013 ), 562 -- 583 . P. Flocchini, D. Ilcinkas, A. Pelc, and N. Santoro. 2007. Computing without communicating: Ring exploration by asynchronous oblivious robots. Algorithmica 65 (2013), 562--583.","journal-title":"Algorithmica"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v48:3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13284-1_15"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1043"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Ta-Shma A.","unstructured":"A. Ta-Shma and U. Zwick . 2007. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07) , 599--608. A. Ta-Shma and U. Zwick. 2007. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07), 599--608."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.481599"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594581","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2594581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:00:53Z","timestamp":1750215653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,30]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,11,17]]}},"alternative-id":["10.1145\/2594581"],"URL":"https:\/\/doi.org\/10.1145\/2594581","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,30]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}