On the advice complexity of the online L(2,1)-coloring problem on paths and cycles
DOI10.1016/J.TCS.2014.06.027zbMATH Open1382.68099OpenAlexW1998894390MaRDI QIDQ744081FDOQ744081
Authors: Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, Sacha Krug, Björn Steffen 
Publication date: 6 October 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.06.027
Recommendations
- On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
- Advice complexity of online coloring for paths
- Advice complexity of the online coloring problem
- Online coloring of bipartite graphs with and without advice
- Online coloring of bipartite graphs with and without advice
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Advice complexity of online coloring for paths
- On the advice complexity of the knapsack problem
- On online algorithms with advice for the \(k\)-server problem
- On the advice complexity of the set cover problem
- Online coloring of bipartite graphs with and without advice
- On the advice complexity of the \(k\)-server problem
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- Advice complexity of the online coloring problem
- Measuring the problem-relevant information in input
- Labelling Graphs with a Condition at Distance 2
- Combinatorial Geometry and Graph Theory
- A survey on labeling graphs with a condition at distance two
- Approximations for -Colorings of Graphs
- Title not available (Why is that?)
- Online Computation with Advice
- Advice complexity and barely random algorithms
- On the power of randomness versus advice in online computation
Cited In (10)
- On the advice complexity of the online dominating set problem
- On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
- Online multi-coloring with advice
- Online Minimum Spanning Tree with Advice
- Advice complexity of online coloring for paths
- On energy-efficient computations with advice
- On the Advice Complexity of Online Edge- and Node-Deletion Problems
- On the advice complexity of the \(k\)-server problem under sparse metrics
- The secretary problem with reservation costs
- Online \(L(2,1)\)-coloring problem on paths with restricted size of memory
This page was built for publication: On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744081)
