Online coloring known graphs (Q1967115)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Online coloring known graphs |
scientific article |
Statements
Online coloring known graphs (English)
0 references
12 March 2000
0 references
Summary: The problem of online coloring an unknown graph is known to be hard. Here we consider the problem of online coloring in the relaxed situation where the input must be isomorphic to a given known graph. All that foils a computationally powerful player is that it is not known to which sections of the graph the vertices to be colored belong. We show that the performance ratio of any online coloring algorithm with advance knowledge of the input graph is at least \(\Omega(N/\log^2N)\), where \(N\) is the number of vertices. This matches and generalizes the bound for the case of an unknown input graph. We also show that any online independent set algorithm has a performance ratio at least \(N/8\).
0 references
graph coloring
0 references
online algorithms
0 references
online coloring
0 references
performance ratio
0 references
online independent set algorithm
0 references