Online Minimum Spanning Tree with Advice
DOI10.1142/S0129054118410034zbMATH Open1397.68134OpenAlexW2809834751MaRDI QIDQ5895056FDOQ5895056
Authors: Maria Paola Bianchi, Tatjana Brülisauer, Dennis Komm, Beatrice Palano, 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
Recommendations
- Online minimum spanning tree with advice (extended abstract)
- Minimum spanning trees
- An optimal minimum spanning tree algorithm
- scientific article; zbMATH DE number 1670813
- On the minimum diameter spanning tree problem
- Minimum spanning hypertrees
- Minimal spanning trees
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Spanning trees with minimum weighted degrees
Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Title not available (Why is that?)
- Advice complexity of online coloring for paths
- Online graph exploration with advice
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- Online coloring of bipartite graphs with and without advice
- Advice complexity of the online coloring problem
- Advice complexity and barely random algorithms
- Measuring the problem-relevant information in input
- Online computation with advice
- The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
- Universal codeword sets and representations of the integers
- Treasure hunt 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
- On the advice complexity of the \(k\)-server problem
- On the power of advice and randomization for the disjoint path allocation problem
- Advice complexity for a class of online problems
- Randomization can be as helpful as a glimpse of the future in online computation
- Online algorithms with advice: the tape model
- On the power of randomness versus advice in online computation
- The power of recourse for online MST and TSP
- On an Online Spanning Tree Problem in Randomly Weighted Graphs
- Advice complexity of maximum independent set in sparse and bipartite graphs
- Tight bounds for the advice complexity of the online minimum Steiner tree problem
- Online minimum spanning tree with advice (extended abstract)
Cited In (7)
- The power of recourse for online MST and TSP
- Online minimum spanning trees with weight predictions
- Advice complexity of adaptive priority algorithms
- The secretary problem with reservation costs
- Tight bounds for the advice complexity of the online minimum Steiner tree problem
- Online minimum spanning tree with advice (extended abstract)
- On an Online Spanning Tree Problem in Randomly Weighted Graphs
This page was built for publication: Online Minimum Spanning Tree with Advice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895056)
