On the advice complexity of the online dominating set problem
From MaRDI portal
Publication:1998864
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)
Recommendations
- On the Advice Complexity of Online Problems
- Advice complexity for a class of online problems
- The advice complexity of a class of hard online problems
- Advice complexity of the online induced subgraph problem
- On online algorithms with advice for the k-server problem
- On online algorithms with advice for the \(k\)-server problem
- Tight bounds for the advice complexity of the online minimum Steiner tree problem
- Improved analysis of the online set cover problem with advice
- On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
- On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
Cites work
- Advice complexity of the online coloring problem
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Call admission problems on grids with advice (extended abstract)
- Call admission problems on trees with advice (extended abstract)
- Computing the domination number of grid graphs
- How Much Information about the Future Is Needed?
- scientific article; zbMATH DE number 3525174 (Why is no real title available?)
- scientific article; zbMATH DE number 1232130 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 3358495 (Why is no real title available?)
- Information complexity of online problems
- On advice complexity of the k-server problem under sparse metrics
- On online algorithms with advice for the \(k\)-server problem
- On the advice complexity of buffer management
- On the Advice Complexity of Online Problems
- On the advice complexity of the k-server problem
- On the power of advice and randomization for the disjoint path allocation problem
- On-line algorithms for the dominating set problem
- Online algorithms with advice: the tape model
- Online bin packing with advice
- Online coloring of bipartite graphs with and without advice
- Online computation with advice
- Online dominating set
- Randomization can be as helpful as a glimpse of the future in online computation
- The advice complexity of a class of hard online problems
- The online knapsack problem: advice and randomization
- The string guessing problem as a method to prove lower bounds on the advice complexity
- The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
- Universal codeword sets and representations of the integers
- Weighted online problems with advice
Cited in
(10)- Online dominating set
- Advice complexity of online non-crossing matching
- The secretary problem with reservation costs
- Independent set with advice: the impact of graph knowledge (extended abstract)
- On the Advice Complexity of Online Problems
- scientific article; zbMATH DE number 1302187 (Why is no real title available?)
- Improved bounds for online dominating sets of trees
- Online Dominating Set
- Online landmark replacement for out-of-sample dimensionality reduction methods
- Online unbounded knapsack
This page was built for publication: On the advice complexity of the online dominating set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1998864)
