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

"Paltis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> "Rob Pratt" <[EMAIL PROTECTED]> wrote in message
news:<[EMAIL PROTECTED]>...
> > "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
>
> Thank you Rob,
>
> Unfortunately I forgot a constraint which is
> I have a fixed number Nb of
> black and Nw of white vertices so a stable configuration
> must contain this number of vertices of each color.
> And of course I need the closer to optimal solution.
>
> Is there freeware to solve the problem as you code it?
> Does Matlab do that?
> (I'm new to this domain and I don't know which
> are the "classical" tools or method to solve that).
>
> Paltis


You need only include one additional constraint:
sum x(i) = Nb.

(The "other" one, sum (1 - x(i)) = Nw, is equivalent since every node is
colored black or white.)

I don't know of any free tools, and I don't know whether Matlab will solve
it.


Rob Pratt