Online Minimum Spanning Tree with Advice

DOI10.1142/S0129054118410034MaRDI QIDQ5895056zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

advice complexityonline algorithmonline minimum spanning tree problem

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• Advice complexity and barely random algorithms
• Advice complexity for a class of online problems
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Advice complexity of online coloring for paths
• Advice complexity of the online coloring problem
• Information complexity of online problems
• Measuring the problem-relevant information in input
• On an Online Spanning Tree Problem in Randomly Weighted Graphs
• On the Advice Complexity of Online Problems
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• On the power of advice and randomization for the disjoint path allocation problem
• On the power of randomness versus advice in online computation
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Online algorithms with advice: the tape model
• Online coloring of bipartite graphs with and without advice
• Online computation with advice
• Online graph exploration with advice
• Online minimum spanning tree with advice (extended abstract)
• Randomization can be as helpful as a glimpse of the future in online computation
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• The power of recourse for online MST and TSP
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Tight bounds for the advice complexity of the online minimum Steiner tree problem
• Treasure hunt with advice
• Universal codeword sets and representations of the integers

Cited in

(7)

• On an Online Spanning Tree Problem in Randomly Weighted Graphs
• 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)

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)