Alternative Color Selection Schemes
It is possible to define a greedy coloring algorithm in which the vertices of the given graph are colored in a given sequence but in which the color chosen for each vertex is not necessarily the first available color; alternative color selection strategies have been studied within the framework of online algorithms. In the online graph-coloring problem, vertices of a graph are presented one at a time in an arbitrary order to a coloring algorithm; the algorithm must choose a color for each vertex, based only on the colors of and adjacencies among already-processed vertices. In this context, one measures the quality of a color selection strategy by its competitive ratio, the ratio between the number of colors it uses and the optimal number of colors for the given graph.
If no additional restrictions on the graph are given, the optimal competitive ratio is only slightly sublinear. However, for interval graphs, a constant competitive ratio is possible, while for bipartite graphs and sparse graphs a logarithmic ratio can be achieved. Indeed, for sparse graphs, the standard greedy coloring strategy of choosing the first available color achieves this competitive ratio, and it is possible to prove a matching lower bound on the competitive ratio of any online coloring algorithm.
Read more about this topic: Greedy Coloring
Famous quotes containing the words alternative, color, selection and/or schemes:
“If you have abandoned one faith, do not abandon all faith. There is always an alternative to the faith we lose. Or is it the same faith under another mask?”
—Graham Greene (19041991)
“The most refined skills of color printing, the intricate techniques of wide-angle photography, provide us pictures of trivia bigger and more real than life. We forget that we see trivia and notice only that the reproduction is so good. Man fulfils his dream and by photographic magic produces a precise image of the Grand Canyon. The result is not that he adores nature or beauty the more. Instead he adores his cameraand himself.”
—Daniel J. Boorstin (b. 1914)
“When you consider the radiance, that it does not withhold
itself but pours its abundance without selection into every
nook and cranny”
—Archie Randolph Ammons (b. 1926)
“Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.”
—James Conant (18931978)