Online Graph Coloring Against a Randomized Adversary

DOI10.1142/S0129054118410058zbMath1397.68229OpenAlexW2809805937MaRDI 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

zbMATH Keywords

randomizationinformationgraph coloringonline computation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (2)

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

This page was built for publication: Online Graph Coloring Against a Randomized Adversary