[Lemon-devel] Edge coloring
Ben Strasser
mail at ben-strasser.net
Sat May 22 16:43:57 CEST 2010
Hello,
for a project I am working on I had to implement a couple of edge
coloring algorithms. If there is any interest I could LEMON-ify them.
A valid edge coloring is a coloring of the edges so that each node has
no two incident edges colored in the same way.
What is implemented is:
* An edge map to store valid colorings and that supports the queries
needed by the algorithms in a fast way.
* An algorithm that colors bipartite graphs using at most as many colors
as the maximum node degree.
* Vizing's algorithm to color general simple graphs using at most as
many colors as the maximum node degree + 1.
* Test cases
Both algorithms are in O(m*n)
For general simple graphs it is not always possible to color them using
only maximum node degree. An example is K_3. Determining if this is
possible is NP-hard so Vizing's algorithm seems to be the best you can
get within polynomial time.
I've attached my code.
Best regards,
Ben Strasser
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vizing.zip
Type: application/zip
Size: 3475 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-devel/attachments/20100522/87b91020/attachment.zip>
More information about the Lemon-devel
mailing list