On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
type: Item
instance of: scholarly article
title: On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
zbMATH Open document ID: 1382.68099
author: Maria Paola Bianchi
author: Hans-Joachim Böckenhauer
author: Juraj Hromkovič
author: Sacha Krug
author: Björn Steffen
published in: Theoretical Computer Science
publication date: 2014-10-06T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 6351422
zbMATH Keywords: online coloring
zbMATH Keywords: frequency assignment
zbMATH Keywords: advice complexity
zbMATH Keywords: randomized algorithms
MaRDI profile type: Publication
full work available at URL: j.tcs.2014.06.027
OpenAlex ID: W1998894390
cites work: Online Coloring of Bipartite Graphs with and without Advice
cites work: Approximations for -Colorings of Graphs
cites work: On the Advice Complexity of the Knapsack Problem
cites work: On the Advice Complexity of the k-Server Problem
cites work: On the Advice Complexity of Online Problems
cites work: On the Power of Randomness versus Advice in Online Computation
cites work: Q4223058
cites work: Combinatorial Geometry and Graph Theory
cites work: Measuring the problem-relevant information in input
cites work: Online Computation with Advice
cites work: Advice Complexity of Online Coloring for Paths
cites work: Labelling Graphs with a Condition at Distance 2
cites work: Information Complexity of Online Problems
cites work: Advice Complexity and Barely Random Algorithms
cites work: On the Advice Complexity of the Set Cover Problem
cites work: Q3145804
cites work: On Online Algorithms with Advice for the k-Server Problem
cites work: Advice Complexity of the Online Coloring Problem
cites work: A survey on labeling graphs with a condition at distance two
DOI: 10.1016/J.TCS.2014.06.027
description: scientific article; zbMATH DE number 6351422