Online coloring of bipartite graphs with and without advice

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

zbMATH Keywords

bipartite graphlower boundsadvice complexityonline coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27)

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

• OEIS

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?