[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