Finding independent sets in a graph using continuous multivariable polynomial formulations Academic Article

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 x0 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(x0) and H(x0), 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.

authors

• Butenko, Sergiy

published proceedings

• JOURNAL OF GLOBAL OPTIMIZATION

author list (cited authors)

• Abello, J., Butenko, S., Pardalos, P. M., & Resende, M.

citation count

• 37

complete list of authors

• Abello, J||Butenko, S||Pardalos, PM||Resende, MGC

publication date

• October 2001

publisher

• Springer Nature  Publisher

published in

• Journal of Global Optimization  Journal

keywords

• Continuous Approach
• Global Optimization
• Maximum Independent Set

Digital Object Identifier (DOI)

• 10.1023/A:1011968411281

start page

• 111

end page

• 137

volume

• 21

issue

• 2

URL

• http://dx.doi.org/10.1023/a:1011968411281