[EMAIL PROTECTED] wrote: > 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. >
*Wow* I'd be really happy with getting chromatic number and chromatic polynomial into the graph theory stuff. I've been sort of embarrassed we didn't have it :) Jason --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
