On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
From MaRDI portal
Publication:744081
DOI10.1016/j.tcs.2014.06.027zbMath1382.68099OpenAlexW1998894390MaRDI QIDQ744081
Björn Steffen, Juraj Hromkovič, Sacha Krug, Maria Paola Bianchi, Hans-Joachim Böckenhauer
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
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (7)
On Energy-Efficient Computations With Advice ⋮ Online \(L(2,1)\)-coloring problem on paths with restricted size of memory ⋮ On the Advice Complexity of Online Edge- and Node-Deletion Problems ⋮ The secretary problem with reservation costs ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Online Minimum Spanning Tree with Advice ⋮ Online multi-coloring with advice
Cites Work
- Unnamed Item
- Unnamed Item
- A survey on labeling graphs with a condition at distance two
- 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
- Advice Complexity and Barely Random Algorithms
- On the Power of Randomness versus Advice in Online Computation
- Information Complexity of Online Problems
- Online Computation with Advice
- On the Advice Complexity of Online Problems
- Labelling Graphs with a Condition at Distance 2
- Approximations for -Colorings of Graphs
- Advice Complexity of the Online Coloring Problem
- Measuring the problem-relevant information in input
- Combinatorial Geometry and Graph Theory
This page was built for publication: On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
