Advice Complexity of Online Coloring for Paths

DOI10.1007/978-3-642-28332-1_20zbMath1351.68312OpenAlexW179266002MaRDI QIDQ2890195

Michal Forišek, Lucia Keller, Monika Steinová

Publication date: 8 June 2012

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.303.2608

zbMATH Keywords

advice complexitypartial coloringonline graph coloring

Mathematics Subject Classification ID

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

Related Items (16)

Online Multi-Coloring with Advice ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ 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 ⋮ Online coloring of bipartite graphs with and without advice ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ On the list update problem with advice ⋮ Online Minimum Spanning Tree with Advice ⋮ On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles ⋮ The string guessing problem as a method to prove lower bounds on the advice complexity ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics ⋮ Online multi-coloring with advice ⋮ Online bin packing with advice

This page was built for publication: Advice Complexity of Online Coloring for Paths