COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 4 years ago

#370 new enhancement

Edge coloring algorithms

Reported by: Ben Strasser Owned by: alpar
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc: mail@…
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 8 years ago.

Download all attachments as: .zip

Change History (2)

Changed 8 years ago by alpar

comment:1 Changed 4 years ago by deba

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release
Note: See TracTickets for help on using tickets.