{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:29Z","timestamp":1759638929765},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> In the online minimum spanning tree problem, a graph is revealed vertex by vertex; together with every vertex, all edges to vertices that are already known are given, and an online algorithm must irrevocably choose a subset of them as a part of its solution. The advice complexity of an online problem is a means to quantify the information that needs to be extracted from the input to achieve good results. For a graph of size [Formula: see text], we show an asymptotically tight bound of [Formula: see text] on the number of advice bits to produce an optimal solution for any given graph. For particular graph classes, e.g., with bounded degree or a restricted edge weight function, we prove that the upper bound can be drastically reduced; e.g., [Formula: see text] advice bits allow to compute an optimal result if the weight function equals the Euclidean distance; if the graph is complete and has two different edge weights, even a logarithmic number suffices. Some of these results make use of the optimality of Kruskal\u2019s algorithm for the offline setting. We also study the trade-off between the number of advice bits and the achievable competitive ratio. To this end, we perform a reduction from another online problem to obtain a linear lower bound on the advice complexity for any near-optimal solution. Using our results finally allows us to give a lower bound on the expected competitive ratio of any randomized online algorithm for the problem, even on graphs with three different edge weights. <\/jats:p>","DOI":"10.1142\/s0129054118410034","type":"journal-article","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T07:14:49Z","timestamp":1530256489000},"page":"505-527","source":"Crossref","is-referenced-by-count":5,"title":["Online Minimum Spanning Tree with Advice"],"prefix":"10.1142","volume":"29","author":[{"given":"Maria Paola","family":"Bianchi","sequence":"first","affiliation":[{"name":"Z\u00fchlke Engineering AG, Switzerland"}]},{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich, Switzerland"}]},{"given":"Tatjana","family":"Br\u00fclisauer","sequence":"additional","affiliation":[{"name":"Google Inc., Zurich, Switzerland"}]},{"given":"Dennis","family":"Komm","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich, Switzerland"}]},{"given":"Beatrice","family":"Palano","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica \u201cGiovanni Degli Antoni\u201d, Universit\u00e0 degli Studi di Milano via Comelico 39, 20135 Milano, Italy"}]}],"member":"219","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"S0129054118410034BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9819-7"},{"key":"S0129054118410034BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.027"},{"key":"S0129054118410034BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31644-9_2"},{"key":"S0129054118410034BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.006"},{"key":"S0129054118410034BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.03.001"},{"key":"S0129054118410034BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.01.001"},{"key":"S0129054118410034BIB012","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998"},{"key":"S0129054118410034BIB013","doi-asserted-by":"publisher","DOI":"10.1145\/3056461"},{"key":"S0129054118410034BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9592-2"},{"issue":"3","key":"S0129054118410034BIB018","first-page":"585","volume":"43","author":"Dobrev S.","year":"2009","journal-title":"RAIRO ITA"},{"key":"S0129054118410034BIB020","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"S0129054118410034BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.007"},{"key":"S0129054118410034BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42749-2"},{"key":"S0129054118410034BIB025","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011105"},{"key":"S0129054118410034BIB027","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"S0129054118410034BIB028","doi-asserted-by":"publisher","DOI":"10.1137\/130917703"},{"key":"S0129054118410034BIB030","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600770X"},{"key":"S0129054118410034BIB032","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"S0129054118410034BIB035","volume-title":"Data Structures and Network Algorithms","author":"Tarjan R. E.","year":"1984"},{"key":"S0129054118410034BIB036","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90142-V"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118410034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:44:09Z","timestamp":1565120649000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118410034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":20,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2018,6,29]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0129054118410034"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118410034","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}