I've found a nice implementation of the DLX algorithm, which "quickly" solves
the NP-Complete exact cover problem. For those who aren't in Seattle and
haven't heard me blathering on and on and on and on about how awesome DLX is...
Let M be a binary matrix. An exact cover is a subset of the rows of the matrix
who sum (exactly) to the vector 1,1,...,1.
For example, an exact cover of
1010
1100
1011
0101
0111
is
1010
0101
Just now, I've completed wrapping Antti Ajanki's implementation of DLX so that
one can easily compute the exact cover of a Sage matrix, and I've constructed a
mapping from the graph coloring problem into the exact cover problem. Further,
I've applied that to compute the chromatic number and chromatic polynomial of
graphs. I think there is sufficient interest in this (ref #1313, #1311).
Arguments for including Ajanki's code:
1) It's the only Python implementation of DLX I've seen.
2) I emailed the author, who happily added the "or later" bit after the GPL2
3) With my Sage Matrix -> DLXMatrix code (plus docstrings to everything I
added), the file dlx.py is only 8kB!
4) It will resolve tickets #1311 and #1313
So - I'm thinking this should be added to the combinat directory (of course,
the graph-oriented stuff will go into graphs). I'll file a ticket & some
patches today if nobody objects.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
