#5913: implement graph coloring in sage
--------------------------+-------------------------------------------------
Reporter: was | Owner: rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.0
Component: graph theory | Keywords:
--------------------------+-------------------------------------------------
Comment(by was):
Some offlist emails about this
{{{
I agree, graph coloring is rather important. You might want to look at
http://www.cs.ualberta.ca/~joe/Coloring/ which has a lot of good links.
As a stop-gap, it's possible to easily transform a graph-coloring problem
into a satisfiability problem and hand it to a SAT solver (like minisat).
This works ok for fairly small graphs, but more specialized algorithms
seem to work much better when the graphs get at all large.
Victor
Godsil had suggested looking at Joe Culberson's program a while ago,
but as far as I know, nobody has looked into this.
( http://www.cs.ualberta.ca/~joe/Coloring/Colorsrc/index.html )
I can bring this up during the Friday session as an alternative
project for someone to try if you want.
Robert L. Miller
It looks like Joe Culberson's programs don't have a clearly defined
license, just something kind of "as is"/no-warranty -ish. Maybe you
should email him and ask him to allow us to distribute it under
GPLv2+...
Another thing to look at is the recent paper of Miroslav Velev (which I've
attached). To implement this it would involve implementing his algorithms
(probably in SAGE) for translating the graph coloring problem into SAT
input and then passing it to Minisat. He says that by his encodings he's
gotten speedups of 3 orders of magnitude, and is competitive (or better)
than the existing coloring programs.
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5913#comment:1>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
