Finding independent sets in a graph using continuous multivariable polynomial formulations.

DOI10.1023/A:1011968411281zbMath1068.05049MaRDI QIDQ5954199

Sergiy I. Butenko, James Abello, Panos M. Pardalos, Mauricio G. C. Resende

Publication date: 2001

Published in: Journal of Global Optimization (Search for Journal in Brave)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (21)

On characterization of maximal independent sets via quadratic optimization ⋮ New results on the equivalence between zero-one programming and continuous concave programming ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ An exact penalty global optimization approach for mixed-integer programming problems ⋮ Continuous reformulations for zero-one programming problems ⋮ An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach ⋮ A new trust region technique for the maximum weight clique problem ⋮ The fundamental theorem of linear programming: extensions and applications ⋮ On an exact penalty function method for nonlinear mixed discrete programming problems and its applications in search engine advertising problems ⋮ On a polynomial fractional formulation for independence number of a graph ⋮ Independent sets in graphs ⋮ Constructing test functions for global optimization using continuous formulations of graph problems ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ Exact penalty functions for nonlinear integer programming problems ⋮ A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming ⋮ A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs ⋮ A characterization of the weighted Lovász number based on convex quadratic programming ⋮ Novel approaches for analyzing biological networks ⋮ Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of Linear Programming ⋮ Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem ⋮ The clique problem for graphs with a few eigenvalues of the same sign

This page was built for publication: Finding independent sets in a graph using continuous multivariable polynomial formulations.