On the advice complexity of the online dominating set problem
DOI10.1016/j.tcs.2021.01.022zbMath1497.68579OpenAlexW3122069597MaRDI QIDQ1998864
Sacha Krug, Walter Unger, Hans-Joachim Böckenhauer, Juraj Hromkovič
Publication date: 9 March 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.01.022
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online bin packing with advice
- On-line algorithms for the dominating set problem
- Online algorithms with advice: the tape model
- Online computation with advice
- Computing the domination number of grid graphs
- Weighted online problems with advice
- The string guessing problem as a method to prove lower bounds on the advice complexity
- The advice complexity of a class of hard online problems
- Online dominating set
- Call admission problems on grids with advice (extended abstract)
- Call admission problems on trees with advice (extended abstract)
- The online knapsack problem: advice and randomization
- On Advice Complexity of the k-server Problem under Sparse Metrics
- On Online Algorithms with Advice for the k-Server Problem
- Online Coloring of Bipartite Graphs with and without Advice
- On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
- On the Advice Complexity of the k-Server Problem
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- Universal codeword sets and representations of the integers
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- On the Advice Complexity of Buffer Management
- Advice Complexity of the Online Coloring Problem
- The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
- How Much Information about the Future Is Needed?
This page was built for publication: On the advice complexity of the online dominating set problem
