{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T22:29:03Z","timestamp":1772317743585,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            We address the problem of constrained exploration of an unknown graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) from a given start node\n            <jats:italic>s<\/jats:italic>\n            with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, for example, it cannot jump between nonadjacent nodes. In the tethered robot case, if the tether (rope) has length\n            <jats:italic>l<\/jats:italic>\n            , then the robot must remain within distance\n            <jats:italic>l<\/jats:italic>\n            from the start node\n            <jats:italic>s<\/jats:italic>\n            . In the second variation, a fuel tank of limited capacity forces the robot to return to\n            <jats:italic>s<\/jats:italic>\n            after traversing\n            <jats:italic>C<\/jats:italic>\n            edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot that explores the graph in \u0398(|\n            <jats:italic>E<\/jats:italic>\n            |) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a \u0398(|\n            <jats:italic>E<\/jats:italic>\n            |) algorithm. This improves on the previous best-known bound of\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>E<\/jats:italic>\n            | + |\n            <jats:italic>V<\/jats:italic>\n            |log\n            <jats:sup>2<\/jats:sup>\n            |\n            <jats:italic>V<\/jats:italic>\n            |). Since the lower bound for the graph exploration problems is \u2126(|\n            <jats:italic>E<\/jats:italic>\n            |), our algorithm is optimal within a constant factor.\n          <\/jats:p>","DOI":"10.1145\/1159892.1159897","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"380-402","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Optimal constrained graph exploration"],"prefix":"10.1145","volume":"2","author":[{"given":"Christian A.","family":"Duncan","sequence":"first","affiliation":[{"name":"University of Miami, Miami, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen G.","family":"Kobourov","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. S. Anil","family":"Kumar","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, VA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"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.1016\/0166-218X(95)00054-U"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)89161-5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794271898"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2795"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/279943.279998"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1039"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3081"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Bender M. A.","unstructured":"Bender , M. A. , and Slonim , D. K . 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). IEEE Computer Society Press , Los Alamitos, CA, 75--87. Bender, M. A., and Slonim, D. K. 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). IEEE Computer Society Press, Los Alamitos, CA, 75--87."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 7th Annual Symposium on Discrete Algorithms (SODA). ACM","author":"Berman P.","unstructured":"Berman , P. , Blum , A. , Fiat , A. , Karloff , H. , Ros\u00e9n , A. , and Saks , M . 1996. Randomized robot navigation algorithms . In Proceedings of the 7th Annual Symposium on Discrete Algorithms (SODA). ACM , New York, 75--84. Berman, P., Blum, A., Fiat, A., Karloff, H., Ros\u00e9n, A., and Saks, M. 1996. Randomized robot navigation algorithms. In Proceedings of the 7th Annual Symposium on Discrete Algorithms (SODA). ACM, New York, 75--84."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993411"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290593"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194931"},{"key":"e_1_2_1_14_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 1990. Introduction to Algorithms. MIT Press\/McGraw-Hill New York.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 1990. Introduction to Algorithms. MIT Press\/McGraw-Hill New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274788"},{"key":"e_1_2_1_16_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_17_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Duncan C. A.","unstructured":"Duncan , C. A. , Kobourov , S. G. , and Kumar , V. S. A. 2001. Optimal constrained graph exploration . In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 807--814. Duncan, C. A., Kobourov, S. G., and Kumar, V. S. A. 2001. Optimal constrained graph exploration. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 807--814."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Fraigniaud P. Gasieniec L. Kowalski D. R. and Pelc A. 2004. Collective tree exploration. In LATIN. 141--151.  Fraigniaud P. Gasieniec L. Kowalski D. R. and Pelc A. 2004. Collective tree exploration. In LATIN. 141--151.","DOI":"10.1007\/978-3-540-24698-5_18"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799348670"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1043"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90263-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Rao N. S. V. Kareti S. Shi W. and Iyengar S. S. 1993. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Tech. Rep. Oak Ridge National Laboratory. July. ORNL\/TM-12410.  Rao N. S. V. Kareti S. Shi W. and Iyengar S. S. 1993. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Tech. Rep. Oak Ridge National Laboratory. July. ORNL\/TM-12410.","DOI":"10.2172\/10180101"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1021"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1159892.1159897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:42:41Z","timestamp":1672260161000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1159892.1159897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1159892.1159897"],"URL":"https:\/\/doi.org\/10.1145\/1159892.1159897","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}