{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:14Z","timestamp":1759638374099},"reference-count":28,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p> We consider the problem of exploration of networks, some of whose edges are faulty. A mobile agent, situated at a starting node and unaware of which edges are faulty, has to explore the connected fault-free component of this node by visiting all of its nodes. The cost of the exploration is the number of edge traversals. For a given network and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An exploration algorithm, for a given network and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any ring, and show that, for networks modeled by hamiltonian graphs, the overhead of any DFS exploration is at most 10\/9 times larger than that of a perfectly competitive algorithm. Moreover, for hamiltonian graphs of size at least 24, this overhead is less than 6% larger than that of a perfectly competitive algorithm. <\/jats:p>","DOI":"10.1142\/s0129054116500313","type":"journal-article","created":{"date-parts":[[2017,1,24]],"date-time":"2017-01-24T00:57:32Z","timestamp":1485219452000},"page":"809-827","source":"Crossref","is-referenced-by-count":1,"title":["Exploration of Faulty Hamiltonian Graphs"],"prefix":"10.1142","volume":"27","author":[{"given":"David","family":"Caissy","sequence":"first","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec J8X 3X7, Canada"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec J8X 3X7, Canada"}]}],"member":"219","published-online":{"date-parts":[[2017,1,23]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732428X"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2795"},{"key":"p_3","first-page":"457","volume":"3","author":"Balamohan B.","year":"2011","journal-title":"Alg. and Appl."},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1039"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3081"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194931"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993411"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.011"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008133"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274788"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1109\/70.508436"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.031"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.017"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1002\/net.20095"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.11.022"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1232-z"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0154-y"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1109\/70.105395"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159897"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9341-8"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9065-y"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.024"},{"key":"p_30","doi-asserted-by":"publisher","DOI":"10.1002\/net.20233"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1252-0"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1043"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054114500129"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116500313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:52:02Z","timestamp":1565131922000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116500313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11]]},"references-count":28,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2017,1,23]]},"published-print":{"date-parts":[[2016,11]]}},"alternative-id":["10.1142\/S0129054116500313"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116500313","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11]]}}}