J. Abello, S. Butenko, P.M.
Pardalos, and M.G.C. Resende

**J. of Global Optimization, **vol.
21, pp. 111-137, 2001

**ABSTRACT**

Two continuous formulations of the
maximum independent set problem on a graph *G *= *(V ,E) *are
considered. Both cases involve the maximization of an *n*-variable
polynomial over the *n*-dimensional hypercube, where *n *is
the number of nodes in *G*. Two (polynomial) objective functions *F(x)
*and *H(x) *are considered. Given any solution to *x*_{0
}in the hypercube, we propose two polynomial-time algorithms based
on these formulations, for finding maximal independent sets with
cardinality greater than or equal to *F(x*_{0}*) *and *H(x*_{0}*)*,
respectively. A relation between the two approaches is studied and a
more general statement for dominating sets is proved. Results of
preliminary computational experiments for some of the DIMACS clique
benchmark graphs are presented.

Go back

Mauricio G.C. Resende's Home PageLast modified: