Airborne particulate radioactivity monitoring

2014-01-26T01:35:43Z

69.117.113.22: /* CPAM applications: reactor leak detection */

[[Image:Greedy colourings.svg|thumb|right|Two greedy colorings of the same graph using different vertex orders. The right example generalises to 2-colorable graphs with ''n'' vertices, where the greedy algorithm expends <math>n/2</math> colors.]]
In the study of [[graph coloring]] problems in [[mathematics]] and [[computer science]], a '''greedy coloring''' is a coloring of the [[vertex (graph theory)|vertices]] of a [[undirected graph|graph]] formed by a [[greedy algorithm]] that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings do not in general use the minimum number of colors possible; however they have been used in mathematics as a technique for proving other results about colorings and in computer science as a heuristic to find colorings with few colors.

==Greed is not always good==
A [[crown graph]] (a [[complete bipartite graph]] ''K''<sub>''n'',''n''</sub>, with the edges of a [[perfect matching]] removed) is a particularly bad case for greedy coloring: if the vertex ordering places two vertices consecutively whenever they belong to one of the pairs of the removed matching, then a greedy coloring will use ''n'' colors, while the optimal number of colors for this graph is two. There also exist graphs such that with high probability a randomly chosen vertex ordering leads to a number of colors much larger than the minimum.<ref>{{harvtxt|Kučera|1991}}.</ref> Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.

It is NP-complete to determine, for a given graph ''G'' and number ''k'', whether there exists an ordering of the vertices of ''G'' that forces the greedy algorithm to use ''k'' or more colors. In particular, this means that it is difficult to find the worst ordering for ''G''.<ref>{{harvtxt|Zaker|2006}}.</ref>

==Optimal ordering==
The vertices of any graph may always be ordered in such a way that the greedy algorithm produces an optimal coloring. For, given any optimal coloring in which the smallest color set is maximal, the second color set is maximal with respect to the first color set, etc., one may order the vertices by their colors. Then when one uses a greedy algorithm with this order, the resulting coloring is automatically optimal. More strongly, [[perfectly orderable graph]]s (which include [[chordal graph]]s, [[comparability graph]]s, and [[distance-hereditary graph]]s) have an ordering that is optimal both for the graph itself and for all of its [[induced subgraph]]s.<ref>{{harvtxt|Chvátal|1984}}.</ref> However, finding an optimal ordering for an arbitrary graph is [[NP-hard]] (because it could be used to solve the [[NP-complete]] graph coloring problem), and recognizing perfectly orderable graphs is also NP-complete.<ref>{{harvtxt|Middendorf|Pfeiffer|1990}}.</ref> For this reason, heuristics have been used that attempt to reduce the number of colors while not guaranteeing an optimal number of colors.

==Heuristic ordering strategies==
A commonly used ordering for greedy coloring is to choose a vertex ''v'' of minimum [[degree (graph theory)|degree]], order the remaining vertices, and then place ''v'' last in the ordering. If every subgraph of a graph ''G'' contains a vertex of degree at most ''d'', then the greedy coloring for this ordering will use at most ''d'' + 1 colors.<ref>{{harvtxt|Welsh|Powell|1967}}; {{harvtxt|Johnson|1979}}; {{harvtxt|Sysło|1989}}; {{harvtxt|Maffray|2003}}.</ref> The smallest such ''d'' is commonly known as the [[Degeneracy (graph theory)|degeneracy]] of the graph.

For a graph of maximum degree Δ, any greedy coloring will use at most Δ + 1 colors. [[Brooks' theorem]] states that with two exceptions ([[complete graph|cliques]] and [[cycle graph|odd cycles]]) at most Δ colors are needed. One proof of Brooks' theorem involves finding a vertex ordering in which the first two vertices are adjacent to the final vertex but not adjacent to each other, and each subsequent vertex has at least one earlier neighbor. For an ordering with this property, the greedy coloring algorithm uses at most Δ colors.<ref>{{harvtxt|Lovász|1975}}.</ref>

==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 algorithm]]s. 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 analysis (online algorithm)|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.<ref>{{harvtxt|Lovász|Saks|Trotter|1989}}; Sz, {{harvtxt|Vishwanathan|1990}}.</ref> However, for [[interval graph]]s, a constant competitive ratio is possible,<ref>{{harvtxt|Kierstead|Trotter|1981}}.</ref> while for [[bipartite graph]]s and [[sparse graph]]s a logarithmic ratio can be achieved.<ref name="irani">{{harvtxt|Irani|1994}}.</ref> 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.<ref name="irani"/>

==Notes==
{{reflist|2}}

==References==
*{{citation
| last = Chvátal | first = Václav | author-link = Vašek Chvátal
| contribution = Perfectly orderable graphs
| editor1-last = Berge | editor1-first = Claude | editor1-link = Claude Berge
| editor2-last = Chvátal | editor2-first = Václav | editor2-link = Vašek Chvátal
| location = Amsterdam
| pages = 63–68
| publisher = North-Holland
| series = Annals of Discrete Mathematics
| title = Topics in Perfect Graphs
| volume = 21
| year = 1984}}. As cited by {{harvtxt|Maffray|2003}}.
*{{citation
| last = Irani | first = Sandy
| doi = 10.1007/BF01294263
| issue = 1
| journal = Algorithmica
| pages = 53–72
| title = Coloring inductive graphs on-line
| volume = 11
| year = 1994}}.
*{{citation
| last1 = Kierstead | first1 = H. A.
| last2 = Trotter | first2 = W. A.
| journal = Congress. Numer.
| pages = 143–153
| title = An extremal problem in recursive combinatorics
| volume = 33
| year = 1981}}. As cited by {{harvtxt|Irani|1994}}.
*{{citation
| last = Kučera | first = Luděk
| doi = 10.1016/0196-6774(91)90040-6
| issue = 4
| journal = Journal of Algorithms
| pages = 674–684
| title = The greedy coloring is a bad probabilistic algorithm
| volume = 12
| year = 1991}}.
*{{citation
| last = Johnson | first = D. S. | author-link = David S. Johnson
| contribution = Worst case behavior of graph coloring algorithms
| location = Winnipeg
| pages = 513–527
| publisher = Utilitas Mathematica
| title = Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation
| year = 1979}}. As cited by {{harvtxt|Maffray|2003}}.
*{{citation
| last = Lovász | first = L. | author-link = László Lovász
| journal = Journal of Combinatorial Theory, Series B
| pages = 269–271
| title = Three short proofs in graph theory
| volume = 19
| year = 1975
| doi = 10.1016/0095-8956(75)90089-1
| issue = 3}}.
*{{citation
| last1 = Lovász | first1 = L. | author1-link = László Lovász
| last2 = Saks | first2 = M. E.
| last3 = Trotter | first3 = W. A.
| doi = 10.1016/0012-365X(89)90096-4
| issue = 1–3
| journal = Discrete Mathematics
| pages = 319–325
| title = An on-line graph coloring algorithm with sublinear performance ratio
| volume = 75
| year = 1989}}.
*{{citation
| last = Maffray | first = Frédéric
| contribution = On the coloration of perfect graphs
| doi = 10.1007/0-387-22444-0_3
| editor1-last = Reed | editor1-first = Bruce A. | editor1-link = Bruce Reed (mathematician)
| editor2-last = Sales | editor2-first = Cláudia L.
| pages = 65–84
| publisher = Springer-Verlag
| series = CMS Books in Mathematics
| title = Recent Advances in Algorithms and Combinatorics
| volume = 11
| year = 2003
| isbn = 0-387-95434-1}}.
*{{citation
| last1 = Middendorf | first1 = Matthias
| last2 = Pfeiffer | first2 = Frank
| doi = 10.1016/0012-365X(90)90251-C
| issue = 3
| journal = Discrete Mathematics
| pages = 327–333
| title = On the complexity of recognizing perfectly orderable graphs
| volume = 80
| year = 1990}}.
*{{citation
| last = Sysło | first = Maciej M.
| doi = 10.1016/0012-365X(89)90212-4
| issue = 1–2
| journal = Discrete Mathematics
| pages = 241–243
| title = Sequential coloring versus Welsh-Powell bound
| volume = 74
| year = 1989}}.
*{{citation
| last = Vishwanathan | first = S.
| contribution = Randomized online graph coloring
| doi = 10.1109/FSCS.1990.89567
| pages = 464–469
| title = Proc. 31st IEEE Symp. Foundations of Computer Science (FOCS '90)
| volume = 2
| year = 1990
| isbn = 0-8186-2082-X}}.
*{{citation
| last1 = Welsh | first1 = D. J. A.
| last2 = Powell | first2 = M. B.
| doi = 10.1093/comjnl/10.1.85
| issue = 1
| journal = The Computer Journal
| pages = 85–86
| title = An upper bound for the chromatic number of a graph and its application to timetabling problems
| volume = 10
| year = 1967}}.
*{{citation
| last = Zaker | first = Manouchehr
| doi = 10.1016/j.disc.2005.06.044
| issue = 2–3
| journal = Discrete Mathematics
| pages = 3166–3173
| title = Results on the Grundy chromatic number of graphs
| volume = 306
| year = 2006}}.

[[Category:Graph coloring]]

formulasearchengine - User contributions [en]

Airborne particulate radioactivity monitoring