id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,revision
370,Edge coloring algorithms,Ben Strasser,Alpar Juttner,"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
",enhancement,new,major,LEMON 1.5 release,core,hg main,,,,