Online Minimum Spanning Tree with Advice

DOI10.1142/S0129054118410034zbMath1397.68134OpenAlexW2809834751MaRDI QIDQ5895056

Beatrice Palano, Dennis Komm, Maria Paola Bianchi, Tatjana Brülisauer, Hans-Joachim Böckenhauer

Publication date: 24 July 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054118410034

zbMATH Keywords

online algorithmadvice complexityonline minimum spanning tree problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Online minimum spanning trees with weight predictions ⋮ Advice complexity of adaptive priority algorithms ⋮ The secretary problem with reservation costs

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Online coloring of bipartite graphs with and without advice
• Online algorithms with advice: the tape model
• Online computation with advice
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• The string guessing problem as a method to prove lower bounds on the advice complexity
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• Advice complexity of maximum independent set in sparse and bipartite graphs
• On the advice complexity of the \(k\)-server problem
• Advice Complexity of Online Coloring for Paths
• Online Graph Exploration with Advice
• Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem
• On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
• On the Power of Randomness versus Advice in Online Computation
• On an Online Spanning Tree Problem in Randomly Weighted Graphs
• Treasure Hunt with Advice
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• Universal codeword sets and representations of the integers
• Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
• Advice Complexity of the Online Coloring Problem
• Advice Complexity and Barely Random Algorithms
• Measuring the problem-relevant information in input
• Online Minimum Spanning Tree with Advice
• The Power of Recourse for Online MST and TSP

This page was built for publication: Online Minimum Spanning Tree with Advice