wiki:DLF

Version 1 (modified by hauma, 15 years ago) (diff)

Added Distributed Larges First Algorithm for Graph Coloring

Distributed Larges First Algorithm for Graph Coloring

The algorithm in ![1] colors a distributed graph, but requires synchronized rounds. The following extension formulated as message passing algorithm removes the explicit synchronization requirement.

The wiki:IncrementalDLF? algorithm extends this version by allowing changes to the colored graph and fixing the coloring incrementally.

![1] Distributed Largest-First Algorithm for Graph Coloring, Jennie Hansen, Marek Kubale, Łukasz Kuszner, and Adam Nadolski. In Proceedings of the 10th International Euro-Par Conference of Lecture Notes in Computer Science Volume 3149, pages 804-811, Pisa, Italy, August 31 - September 3, 2004, Springer Verlag, Heidelberg, Germany, 2004

Collective procedure: DLF for node k.
   Precondition: Node k is not colored.
   Precondition: All neighbors of k are marked active.

   While (node k is not colored)
      Choose color c as the smalest number [0, 1, ...] not already
         assigned to any neighbor that is not active.
      Choose a random number r;

      Send CHECK(c, deg(k), r) to all active neighbors.
      Receive CHECK(c(n), deg(n), r(n)) from all active neighbors n.

      Compare (c, deg(k), r) against all received parameters.
      If (k has highest priority or color c produces no conflict)
         Send message COLOR(c) to all neighbors.
         Set node k colored.
      Else
         Send message CANCEL() to all neighbors with less priority 
            and all non-conflicting neighbors.

      Call: Receive reply messages.
   End of while

   Call: Receive missing color messages.

   Postcondition: Node k is colored.
   Postcondition: All neighbors have a color assigned.
   Postcondition: All neighbors are not active.

With:

Condition: node x has a higher priority than node y  <=>
   (deg(x), r(x), rank(x)) >,>,> (deg(y), r(y), rank(y))

Procedure: Receive reply messages.
   For all active neighbors n with higher priority or no conflict:
      Call: Receive reply message m from neighbor n.

Procedure: Receive reply message m from neighbor n.
   Receive message m from neighbor n.
   Switch message m:
      COLOR(cn):
         Call: Handle message COLOR(cn).

      CANCEL():
         Do nothing.

Procedure: Receive missing color messages.
   For each active neighbor n: 
      Receive message COLOR(cn) from neighbor n.
      Call: Handle message COLOR(cn) from neighbor n.

Procedure: Handle message COLOR(cn) from neighbor n.
   Assign color cn to neighbor n. 
   Mark color cn as USED.
   Mark neighbor n as not ACTIVE.