Advice Complexity of the Online Coloring Problem

DOI10.1007/978-3-642-38233-8_29zbMath1382.68338OpenAlexW148386696MaRDI QIDQ4924664

Walter Unger, Andreas Sprock, Sebastian Seibert

Publication date: 7 June 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/156343

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items

Online Multi-Coloring with Advice ⋮ On Energy-Efficient Computations With Advice ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ Online \(L(2,1)\)-coloring problem on paths with restricted size of memory ⋮ The advice complexity of a class of hard online problems ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ On the list update problem with advice ⋮ On the advice complexity of the online dominating set problem ⋮ Online Minimum Spanning Tree with Advice ⋮ On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles ⋮ Towards using the history in online computation with advice ⋮ Online multi-coloring with advice ⋮ Online bin packing with advice