Bianchi, Maria Paola Böckenhauer, Hans-Joachim Brülisauer, Tatjana Komm, Dennis Palano, Beatrice 2018 <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’s 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> https://sonar.ch/global/documents/95336 eng info:eu-repo/semantics/altIdentifier/doi/10.1142/s0129054118410034 info:eu-repo/semantics/altIdentifier/issn/0129-0541 International Journal of Foundations of Computer Science. - World Scientific Pub Co Pte Lt. - 2018, vol. 29, no. 04, p. 505-527 Online Minimum Spanning Tree with Advice http://purl.org/coar/resource_type/c_6501