Finding independent sets in a graph using continuous multivariable polynomial formulations

Citation
J. Abello et al., Finding independent sets in a graph using continuous multivariable polynomial formulations, J GLOB OPT, 21(2), 2001, pp. 111-137
Citations number
26
Categorie Soggetti
Engineering Mathematics
Journal title
JOURNAL OF GLOBAL OPTIMIZATION
ISSN journal
09255001 → ACNP
Volume
21
Issue
2
Year of publication
2001
Pages
111 - 137
Database
ISI
SICI code
0925-5001(200110)21:2<111:FISIAG>2.0.ZU;2-Z
Abstract
Two continuous formulations of the maximum independent set problem on a gra ph G=(V,E) are considered. Both cases involve the maximization of an n-vari able 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 consider ed. Given any solution to x(0) in the hypercube, we propose two polynomial- time algorithms based on these formulations, for finding maximal independen t sets with cardinality greater than or equal to F(x(0)) and H(x(0)), respe ctively. A relation between the two approaches is studied and a more genera l statement for dominating sets is proved. Results of preliminary computati onal experiments for some of the DIMACS clique benchmark graphs are present ed.