{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T16:30:15Z","timestamp":1675182615869},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,4]]},"abstract":"<jats:p> A mobile agent starting at an arbitrary node of an m \u00d7 k grid, for 1 &lt; m \u2264 k, has to explore the grid by visiting all its nodes and traversing all edges. The cost of an exploration algorithm is the number of edge traversals by the agent. Nodes of the grid are unlabeled and ports at each node v have distinct numbers in {0,\u2026, d \u2212 1}, where d = 2, 3, 4 is the degree of v. Port numbering is local, i.e., there is no relation between port numbers at different nodes. When visiting a node the agent sees its degree. It also sees the port number by which it enters a node and can choose the port number by which it leaves a visited node. We are interested in deterministic exploration algorithms working at low cost. <\/jats:p><jats:p> We consider the scenario in which the agent is equipped with a stationary token situated at its starting node. The agent sees the token whenever it visits this node. We give an exploration algorithm working at cost O(k<jats:sup>2<\/jats:sup>) for 2 \u00d7 k grids, and at cost O(m<jats:sup>2<\/jats:sup>k), for m \u00d7 k grids, when 2 &lt; m \u2264 k. <\/jats:p>","DOI":"10.1142\/s0129054114500129","type":"journal-article","created":{"date-parts":[[2014,7,25]],"date-time":"2014-07-25T05:48:52Z","timestamp":1406267332000},"page":"247-262","source":"Crossref","is-referenced-by-count":5,"title":["EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN"],"prefix":"10.1142","volume":"25","author":[{"given":"ANDRZEJ","family":"PELC","sequence":"first","affiliation":[{"name":"D\u00e9partement d'informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec J8X 3X7, Canada"}]},{"given":"ANAS","family":"TIANE","sequence":"additional","affiliation":[{"name":"D\u00e9partement d'informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec J8X 3X7, Canada"}]}],"member":"219","published-online":{"date-parts":[[2014,7,24]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732428X"},{"key":"p_2","first-page":"17","volume":"7","author":"Ambuehl C.","year":"2011","journal-title":"ACM Transactions on Algorithms"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00054-U"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)89161-5"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004826"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993411"},{"key":"p_11","first-page":"208","volume":"6410","author":"Chalopin J.","journal-title":"LNCS"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008133"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.011"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.031"},{"key":"p_18","first-page":"195","volume":"5869","author":"Devismes S.","journal-title":"LNCS"},{"key":"p_19","first-page":"64","volume":"7596","author":"Devismes S.","journal-title":"LNCS"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.017"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.007"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9611-5"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1002\/net.20127"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9518-1"},{"key":"p_30","first-page":"183","volume":"6058","author":"Lamani A.","journal-title":"LNCS"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1389"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1043"},{"key":"p_34","first-page":"55","author":"Reingold O.","year":"2008","journal-title":"Journal of the ACM"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114500129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:54:19Z","timestamp":1565200459000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114500129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":24,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2014,7,24]]},"published-print":{"date-parts":[[2014,4]]}},"alternative-id":["10.1142\/S0129054114500129"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114500129","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4]]}}}