Re: need an algo for graph-coloring...

"Rob Pratt" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> "Paltis" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]
> > Hello all,
> >
> > I have a non-oriented connected graph
> > (the only thing I know about it) and
> > I have to color each vertex with either
> > black or white color (only two possible colors).
> >
> > I'm looking for any reference or algorithm
> > (on-line if possible)
> > allowing to color the vertices so that
> > the number of edges connecting two vertices
> > with the same color is minimized.
> >
> > I would prefer "exact" methods, or
> > "approached" methods with proved convergence
> > to a stable locally minimal color configuration.
> >
> > I cross-posted to cellular automata
> > because in 2D cellular automata, a
> > minimal configuration corresponds
> > to a chess-board or alternative parallel strips depending
> > on the neighborhood of a cell, and people there maybe
> > know some simple rule to go from random configuration
> > to such optimal configuration, which could hopefully
> > be applied to graphs.
> >
> > Thank you for your help
> >
> > Paltis
>
>
> The problem can be solved exactly using an integer programming
formulation.
>
> Let x(i) be the color of node i (1 is black, 0 is white).  Let y(i,j) be 1
> if nodes i and j have the same color, 0 otherwise.  We want to minimize
> sum_{i,j} y(i,j) subject to the following constraints (two for each (i,j)
> pair):
>
> x(i) + x(j) - 1 <= y(i,j)
> (1 - x(i)) + (1 - x(j)) - 1 <= y(i,j)
>
> The first constraint ensures that if x(i) = x(j) = 1, then y(i,j) = 1.
> The second constraint ensures that if x(i) = x(j) = 0, then y(i,j) = 1.
> If x(i) and x(j) are different, the objective function will ensure that
> y(i,j) = 0.
>
>
> Rob Pratt


I neglected to mention that each x(i) should be in {0,1}, but the y(i,j)'s
can be relaxed to 0 <= y(i,j) <= 1.  (They will automatically be integer if
the x(i)'s are.)

Rob Pratt