Advice complexity of online coloring for paths

DOI10.1007/978-3-642-28332-1_20MaRDI QIDQ2890195zbMATH OpenOpenAlexFDO

Authors 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 complexityonline graph coloringpartial coloring

Mathematics Subject Classification ID

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

Recommendations

• Advice complexity of the online coloring problem
• Online coloring of bipartite graphs with and without advice
• Online coloring of bipartite graphs with and without advice
• On the advice complexity of coloring bipartite graphs and two-colorable hypergraphs
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles

Cited in

(23)

• The advice complexity of a class of hard online problems
• Online multi-coloring with advice
• Online bin packing with advice
• Online graph coloring with advice and randomized adversary (extended abstract)
• On advice complexity of the k-server problem under sparse metrics
• Online coloring of bipartite graphs with and without advice
• A technique to obtain hardness results for randomized online algorithms -- a survey
• Optimal online edge coloring of planar graphs with advice
• Online graph coloring against a randomized adversary
• Online Multi-Coloring with Advice
• Online multi-coloring on the path revisited
• On the advice complexity of coloring bipartite graphs and two-colorable hypergraphs
• Online coloring of bipartite graphs with and without advice
• Advice complexity of the online coloring problem
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Parameterized and Exact Computation
• Online Minimum Spanning Tree with Advice
• Online L(2,1)-coloring problem on paths with restricted size of memory
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• Tree coloring with predictions
• 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

This page was built for publication: Advice complexity of online coloring for paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2890195)