Suggest effective heuristic (not precise) graph colouring algorithm - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T11:27:15Z http://mathoverflow.net/feeds/question/11562 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm Suggest effective heuristic (not precise) graph colouring algorithm Oleg 2010-01-12T17:31:25Z 2011-07-23T15:25:43Z <p>Can you suggest a good rough graph colouring algorithm? What are the best such algorithms nowadays?</p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/11570#11570 Answer by Mitch for Suggest effective heuristic (not precise) graph colouring algorithm Mitch 2010-01-12T18:08:54Z 2010-01-12T18:08:54Z <p>An interesting approximation algorithm is the one by Wigderson. It shows how to color a 3-colorable graph with $O(\sqrt{n})$ colors. It's very simple:</p> <p>If the maximum degree is less than $\sqrt{n}$, you're done (just color greedily). If there is a node of degree larger than $\sqrt{n}$, you know that it's neighborhood is two-colorable so two-color it and never use those colors again. Remove the vertex and its neighbors from the graph and continue.</p> <p>There have been several follow-up works by Blum and the latest improvements use semidefinite programming.</p> <p>See, for instance, <a href="http://www.cs.cmu.edu/~anupamg/adv-approx/lecture15.pdf" rel="nofollow">http://www.cs.cmu.edu/~anupamg/adv-approx/lecture15.pdf</a></p> <p>or,</p> <p><a href="http://www.cs.princeton.edu/~chlamtac/acc-stoc.ps" rel="nofollow">http://www.cs.princeton.edu/~chlamtac/acc-stoc.ps</a></p> <p>for the semidefinite programming approach.</p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/18000#18000 Answer by Andrew D. King for Suggest effective heuristic (not precise) graph colouring algorithm Andrew D. King 2010-03-12T18:00:31Z 2010-03-12T18:00:31Z <p>For practical non-optimal purposes you might want to look at DSATUR, and this paper, which briefly describes some simple methods: <a href="http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf" rel="nofollow">http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf</a></p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/18017#18017 Answer by Joseph Malkevitch for Suggest effective heuristic (not precise) graph colouring algorithm Joseph Malkevitch 2010-03-12T22:31:45Z 2010-03-12T22:31:45Z <p>You might find this survey article of use:</p> <p><a href="http://www.springerlink.com/content/r66452u84130n423/" rel="nofollow">http://www.springerlink.com/content/r66452u84130n423/</a></p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/36512#36512 Answer by ABh for Suggest effective heuristic (not precise) graph colouring algorithm ABh 2010-08-24T02:02:38Z 2010-08-24T02:02:38Z <p>Oleg, there are also stochastic parallel approaches where you color all vertices simultaneously and randomly and apply the heuristic in parallel to all of the vertices. This mimics parallel distributed information processing in networks.</p> <p>Can you give some details about the heuristic which you are working on?</p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/36514#36514 Answer by Tsuyoshi Ito for Suggest effective heuristic (not precise) graph colouring algorithm Tsuyoshi Ito 2010-08-24T02:21:28Z 2010-08-24T02:21:28Z <p>If “heuristic graph coloring algorithms” means approximation algorithms for the chromatic number, it is very useful to read “A compendium of NP optimization problems” edited by Pierluigi Crescenzi and Viggo Kann (<a href="http://www.csc.kth.se/~viggo/wwwcompendium/node15.html" rel="nofollow">http://www.csc.kth.se/~viggo/wwwcompendium/node15.html</a>), which provides references for the best-known approximability and inapproximability results as of 2000.</p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/36521#36521 Answer by Suresh Venkat for Suggest effective heuristic (not precise) graph colouring algorithm Suresh Venkat 2010-08-24T05:25:12Z 2010-08-24T05:25:12Z <p>There are a number of heuristics that work fairly well. They all work by prescribing some kind of ordering on the vertices, and then coloring the vertices one by one, using the least unused color to color the next one. </p> <ul> <li>First Fit does precisely the above, with an arbitrary initial ordering. It's fast, but needless to say performs rather poorly.</li> <li>LDO orders the vertices in decreasing order of degree, the idea being that the large degree vertices can be colored more easily. </li> <li>SDO (saturation degree ordering) is a variant on LDO where the vertices are ordered in decreasing order by "saturation degree", defined as the number of distinct colors in the vertex neighborhood. </li> <li>IDO (incidence degree ordering) is a variant of SDO where the "degree" of a vertex is defined as the number of colored vertices in its neighborhood. </li> </ul> <p>The latter two heuristics require the order to be rebuilt after each step, and so are more expensive, but there's <a href="http://www.cs.purdue.edu/homes/agebreme/publications/PhDThesis.pdf" rel="nofollow">empirical evidence</a> suggesting that they do reasonably well, especially in parallel. </p> <p>None of these algorithms come with any kind of formal guarantees, so be warned. </p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/71072#71072 Answer by razeyeh razi for Suggest effective heuristic (not precise) graph colouring algorithm razeyeh razi 2011-07-23T15:25:43Z 2011-07-23T15:25:43Z <p>How to write an algorithm for coloring vertices of a graph in C#?</p>