COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 8 weeks ago

#370 new enhancement

Edge coloring algorithms

Reported by: Ben Strasser Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.5 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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

Attachments (1)

vizing.zip (3.4 KB) - added by Alpar Juttner 9 years ago.

Download all attachments as: .zip

Change History (3)

Changed 9 years ago by Alpar Juttner

Attachment: vizing.zip added

comment:1 Changed 5 years ago by Balazs Dezso

Milestone: LEMON 1.3 releaseLEMON 1.4 release

comment:2 Changed 8 weeks ago by Alpar Juttner

Cc: mail@… removed
Milestone: LEMON 1.4 releaseLEMON 1.5 release
Note: See TracTickets for help on using tickets.