On the advice complexity of the online dominating set problem
type: Item
instance of: scholarly article
title: On the advice complexity of the online dominating set problem
zbMATH Open document ID: 1497.68579
author: Hans-Joachim Böckenhauer
author: Sacha Krug
author: Walter Unger
author: Juraj Hromkovič
published in: Theoretical Computer Science
publication date: 2021-03-09T00:00:00Z
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7318710
zbMATH Keywords: advice complexity
zbMATH Keywords: online computation
zbMATH Keywords: competitive analysis
zbMATH Keywords: dominating set
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.01.022
OpenAlex ID: W3122069597
cites work: Computing the domination number of grid graphs
cites work: On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
cites work: Call admission problems on trees with advice (extended abstract)
cites work: Online Coloring of Bipartite Graphs with and without Advice
cites work: The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
cites work: The string guessing problem as a method to prove lower bounds on the advice complexity
cites work: On the Advice Complexity of the k-Server Problem
cites work: On the Advice Complexity of Online Problems
cites work: Online algorithms with advice: the tape model
cites work: The online knapsack problem: advice and randomization
cites work: Call admission problems on grids with advice (extended abstract)
cites work: Q4223058
cites work: Online dominating set
cites work: The advice complexity of a class of hard online problems
cites work: Weighted online problems with advice
cites work: Online bin packing with advice
cites work: How Much Information about the Future Is Needed?
cites work: On the Advice Complexity of Buffer Management
cites work: Universal codeword sets and representations of the integers
cites work: Online computation with advice
cites work: On Advice Complexity of the k-server Problem under Sparse Metrics
cites work: Q4368728
cites work: Q4103133
cites work: Information Complexity of Online Problems
cites work: On-line algorithms for the dominating set problem
cites work: Q5632589
cites work: Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
cites work: On Online Algorithms with Advice for the k-Server Problem
cites work: All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
cites work: Advice Complexity of the Online Coloring Problem
DOI: 10.1016/J.TCS.2021.01.022
Recommended article: On the Advice Complexity of Online Problems
Recommended article: Q2954988
Recommended article: The advice complexity of a class of hard online problems
Recommended article: Advice Complexity of the Online Induced Subgraph Problem
Recommended article: On online algorithms with advice for the \(k\)-server problem
Recommended article: On Online Algorithms with Advice for the k-Server Problem
Recommended article: Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem
Recommended article: Improved analysis of the online set cover problem with advice
Recommended article: On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles
Recommended article: On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
description: scientific article; zbMATH DE number 7318710