On the advice complexity of the online L(2,1)-coloring problem on paths and cycles

DOI10.1016/J.TCS.2014.06.027MaRDI QIDQ744081zbMATH OpenOpenAlexFDO

Authors Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, Sacha Krug, Björn Steffen

Publication date 6 October 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.06.027

zbMATH Keywords

randomized algorithmsadvice complexityonline coloringfrequency assignment

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• Advice complexity of online coloring for paths
• 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

Cites work

• scientific article; zbMATH DE number 6118222 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A survey on labeling graphs with a condition at distance two
• Advice complexity and barely random algorithms
• Advice complexity of online coloring for paths
• Advice complexity of the online coloring problem
• Approximations for  -Colorings of Graphs
• Combinatorial Geometry and Graph Theory
• Information complexity of online problems
• Labelling Graphs with a Condition at Distance 2
• Measuring the problem-relevant information in input
• On online algorithms with advice for the \(k\)-server problem
• On the Advice Complexity of Online Problems
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the knapsack problem
• On the advice complexity of the set cover problem
• On the power of randomness versus advice in online computation
• Online Computation with Advice
• Online coloring of bipartite graphs with and without advice

Cited in

(10)

• Online multi-coloring with advice
• Advice complexity of online coloring for paths
• On the Advice Complexity of Online Edge- and Node-Deletion Problems
• On energy-efficient computations with advice
• 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
• Online \(L(2,1)\)-coloring problem on paths with restricted size of memory
• The secretary problem with reservation costs
• On the advice complexity of the online dominating set problem
• Online Minimum Spanning Tree with Advice

This page was built for publication: On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles

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