Online Graph Coloring Against a Randomized Adversary
From MaRDI portal
Publication:3177338
DOI10.1142/S0129054118410058zbMath1397.68229MaRDI QIDQ3177338
Richard Královič, Rastislav Královič, Elisabet Burjons, Juraj Hromkovič, Walter Unger, Xavier Muñoz
Publication date: 24 July 2018
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054118410058
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
68W20: Randomized algorithms
68W27: Online algorithms; streaming algorithms
Related Items
Vertex coloring of a graph for memory constrained scenarios, Tight bounds for online coloring of basic graph classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online coloring of bipartite graphs with and without advice
- Online computation with advice
- The string guessing problem as a method to prove lower bounds on the advice complexity
- An on-line graph coloring algorithm with sublinear performance ratio
- On the advice complexity of the \(k\)-server problem
- The online knapsack problem: advice and randomization
- The Complexity of Paging Against a Probabilistic Adversary
- Advice Complexity of Online Coloring for Paths
- On the Advice Complexity of the Set Cover Problem
- Online Graph Exploration with Advice
- On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
- Advice Complexity of Fine-Grained Job Shop Scheduling
- Disjoint Path Allocation with Sublinear Advice
- Information Complexity of Online Problems
- A New Algorithm for On-line Coloring Bipartite Graphs
- On the Advice Complexity of Online Problems
- On-line and first fit colorings of graphs
- Randomized online graph coloring
- Beyond Competitive Analysis
- Advice Complexity and Barely Random Algorithms
- Measuring the problem-relevant information in input
