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

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