Online Minimum Spanning Tree with Advice
From MaRDI portal
Publication:5895056
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
Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)
Related Items
Online minimum spanning trees with weight predictions, Advice complexity of adaptive priority algorithms, The secretary problem with reservation costs
Cites Work
- 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
- Unnamed Item
- Unnamed Item
