Online coloring of bipartite graphs with and without advice
From MaRDI portal
Publication:486981
DOI10.1007/s00453-013-9819-7zbMath1314.68404OpenAlexW2038445565MaRDI QIDQ486981
Maria Paola Bianchi, Lucia Keller, Hans-Joachim Böckenhauer, Juraj Hromkovič
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://doc.rero.ch/record/326369/files/453_2013_Article_9819.pdf
Related Items
Online Graph Coloring Against a Randomized Adversary ⋮ Lower Bounds for On-line Graph Colorings ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ The advice complexity of a class of hard online problems ⋮ Tight bounds for online coloring of basic graph classes ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Online Minimum Spanning Tree with Advice ⋮ Online coloring and a new type of adversary for online graph problems ⋮ Tight Bounds for Online Coloring of Basic Graph Classes ⋮ Online coloring and a new type of adversary for online graph problems ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Online bin packing with advice
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An on-line graph coloring algorithm with sublinear performance ratio
- Advice Complexity of Online Coloring for Paths
- On the Advice Complexity of the Knapsack Problem
- Information Complexity of Online Problems
- Online Computation with Advice
- On the Advice Complexity of Online Problems
- On-line and first fit colorings of graphs
- Randomized online graph coloring
- Universal codeword sets and representations of the integers
- Effective coloration
- Advice Complexity and Barely Random Algorithms
- How Much Information about the Future Is Needed?