{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T18:10:28Z","timestamp":1764785428790,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,7,29]],"date-time":"2024-07-29T00:00:00Z","timestamp":1722211200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,29]],"date-time":"2024-07-29T00:00:00Z","timestamp":1722211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"JSPS KAKENHI","award":["19K11819"],"award-info":[{"award-number":["19K11819"]}]},{"DOI":"10.13039\/100014424","name":"Meiji University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100014424","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>online graph exploration problem<\/jats:italic>, which was proposed by Kalyanasundaram and Pruhs (Theor Comput Sci 130(1):125\u2013138, 1994), is defined as follows: Given an edge-weighted undirected connected graph and a specified vertex (called the <jats:italic>origin<\/jats:italic>), the task of an algorithm is to compute a path from the origin to the origin which contains all the vertices of the given graph. The goal of the problem is to find such a path of minimum weight. At each time, an online algorithm knows only the weights of edges each of which consists of visited vertices or vertices adjacent to visited vertices. Fritsch (Inform Process Lett 168:1006096, 2021) showed that the competitive ratio of an online algorithm is at most three for any unicyclic graph. On the other hand, Brandt et\u00a0al. (Theor Comput Sci 839:176\u2013185, 2020) showed a lower bound of two on the competitive ratio for any unicyclic graph. In this paper, we showed the competitive ratio of an online algorithm is at most 5\/2 for any unicyclic graph.<\/jats:p>","DOI":"10.1007\/s10878-024-01192-0","type":"journal-article","created":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T08:02:11Z","timestamp":1722326531000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An improved upper bound for the online graph exploration problem on unicyclic graphs"],"prefix":"10.1007","volume":"48","author":[{"given":"Koji M.","family":"Kobayashi","sequence":"first","affiliation":[]},{"given":"Ying","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,29]]},"reference":[{"issue":"3","key":"1192_CR1","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ipl.2009.10.013","volume":"110","author":"Y Asahiro","year":"2010","unstructured":"Asahiro Y, Miyano E, Miyazaki S, Yoshimuta T (2010) Weighted nearest neighbor algorithms for the graph exploration problem on cycles. Inf Process Lett 110(3):93\u201398","journal-title":"Inf Process Lett"},{"key":"1192_CR2","unstructured":"Balig\u00e1cs J, Disser Y, Heinrich I, Schweitzer P (2023) Exploration of graphs with excluded minors. In: Proceeding of the 31st Annual European Symposium on Algorithms, pp 11:1\u201311:15"},{"key":"1192_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2021.04.003","volume":"868","author":"A Birx","year":"2021","unstructured":"Birx A, Disser Y, Hopp AV, Karousatou C (2021) An improved lower bound for competitive graph exploration. Theor Comput Sci 868:65\u201386","journal-title":"Theor Comput Sci"},{"key":"1192_CR4","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer H.-J, Fuchs J, Unger W (2018) Exploring sparse graphs with advice (extended abstract). In: Proceeding of of the 16th international workshop on approximation and online algorithms, pp 102\u2013117","DOI":"10.1007\/978-3-030-04693-4_7"},{"key":"1192_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer H.-J Fuchs J, Unger W (2022) Exploring sparse graphs with advice. Inform Comput 289, Part A:104950","DOI":"10.1016\/j.ic.2022.104950"},{"key":"1192_CR6","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge"},{"key":"1192_CR7","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.tcs.2020.06.007","volume":"839","author":"S Brandt","year":"2020","unstructured":"Brandt S, Foerster K-T, Maurer J, Wattenhofer R (2020) Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs. Theor Comput Sci 839:176\u2013185","journal-title":"Theor Comput Sci"},{"issue":"4","key":"1192_CR8","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TRO.2011.2121170","volume":"27","author":"P Brass","year":"2011","unstructured":"Brass P, Cabrera-Mora F, Gasparri A, Xiao J (2011) Multirobot tree and graph exploration. IEEE Trans Rob 27(4):707\u2013717","journal-title":"IEEE Trans Rob"},{"key":"1192_CR9","doi-asserted-by":"crossref","unstructured":"Dobrev S, Kr\u00e1lovic\u0306 R, Markou E (2012) Online graph exploration with advice. In: Proceeding of the 19th international colloquium on structural information and communication complexity, pp 267\u2013278","DOI":"10.1007\/978-3-642-31104-8_23"},{"key":"1192_CR10","doi-asserted-by":"crossref","unstructured":"Dynia M, \u0141opusza\u0144ski J, Schindelhauer C (2007) Why robots need maps. In: Proceedings of the 14th international conference on structural information and communication complexity, pp 41\u201350","DOI":"10.1007\/978-3-540-72951-8_5"},{"issue":"3","key":"1192_CR11","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud P, Gasieniec L, Kowalski DR, Pelc A (2006) Collective tree exploration. Networks 48(3):166\u2013177","journal-title":"Networks"},{"key":"1192_CR12","doi-asserted-by":"publisher","first-page":"1006096","DOI":"10.1016\/j.ipl.2021.106096","volume":"168","author":"R Fritsch","year":"2021","unstructured":"Fritsch R (2021) Online graph exploration on trees, unicyclic graphs and cactus graphs. Inf Process Lett 168:1006096","journal-title":"Inf Process Lett"},{"key":"1192_CR13","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/s10878-012-9571-y","volume":"28","author":"Y Higashikawa","year":"2014","unstructured":"Higashikawa Y, Katoh N, Langerman S, Tanigawa S (2014) Online graph exploration algorithms for cycles and trees by multiple searchers. J Comb Optim 28:480\u2013495","journal-title":"J Comb Optim"},{"issue":"1","key":"1192_CR14","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(94)90155-4","volume":"130","author":"B Kalyanasundaram","year":"1994","unstructured":"Kalyanasundaram B, Pruhs KR (1994) Constructing competitive tours from local information. Theor Comput Sci 130(1):125\u2013138","journal-title":"Theor Comput Sci"},{"key":"1192_CR15","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2012.06.034","volume":"463","author":"N Megow","year":"2012","unstructured":"Megow N, Mehlhorn K, Schweitzer P (2012) Online graph exploration: new results on old and new algorithms. Theor Comput Sci 463:62\u201372","journal-title":"Theor Comput Sci"},{"issue":"9","key":"1192_CR16","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1587\/transinf.E92.D.1620","volume":"92","author":"S Miyazaki","year":"2009","unstructured":"Miyazaki S, Morimoto N, Okabe Y (2009) The online graph exploration problem on restricted graphs. IEICE Trans Inf Syst 92(9):1620\u20131627","journal-title":"IEICE Trans Inf Syst"},{"key":"1192_CR17","doi-asserted-by":"crossref","unstructured":"Ortolf C, Schindelhauer C (2012) Online multi-robot exploration of grid graphs with rectangular obstacles. In: Proceedings of the 24th annual ACM symposium on Parallelism in algorithms and architectures, pp 27\u201336","DOI":"10.1145\/2312005.2312010"},{"issue":"3","key":"1192_CR18","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"DJ Rosenkrantz","year":"1977","unstructured":"Rosenkrantz DJ, Stearns RE, Lewis IIPM (1977) An analysis of several heuristics for the traveling salesman problem. SIAM J Comput 6(3):563\u2013581","journal-title":"SIAM J Comput"},{"issue":"2","key":"1192_CR19","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202\u2013208","journal-title":"Commun ACM"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01192-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01192-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01192-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T19:10:39Z","timestamp":1724440239000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01192-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,29]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1192"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01192-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,7,29]]},"assertion":[{"value":"26 June 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"4"}}