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

DOI10.1023/A:1011968411281MaRDI QIDQ5954199zbMATH OpenFDO

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

Publication date 2001

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

Full work available at URL https://doi.org/10.1023/A:1011968411281

Mathematics Subject Classification ID

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

Recommendations

• On a polynomial fractional formulation for independence number of a graph
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• Fast local search for the maximum independent set problem
• An unconstrained binary quadratic programming for the maximum independent set problem
• On characterization of maximal independent sets via quadratic optimization

Cited in

(27)

• On an exact penalty function method for nonlinear mixed discrete programming problems and its applications in search engine advertising problems
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• A novel evolutionary formulation of the maximum independent set problem
• An exact penalty global optimization approach for mixed-integer programming problems
• Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
• The clique problem for graphs with a few eigenvalues of the same sign
• On characterization of maximal independent sets via quadratic optimization
• A new trust region technique for the maximum weight clique problem
• Using critical sets to solve the maximum independent set problem
• On a polynomial fractional formulation for independence number of a graph
• Novel approaches for analyzing biological networks
• Continuous quadratic programming formulations of optimization problems on graphs
• A characterization of the weighted version of McEliece-Rodemich-Rumsey-Schrijver number based on convex quadratic programming
• Solving the \(k\)-independent sets problem of graphs by Gröbner bases
• An unconstrained binary quadratic programming for the maximum independent set problem
• The fundamental theorem of linear programming: extensions and applications
• Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of Linear Programming
• Continuous reformulations for zero-one programming problems
• An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
• scientific article; zbMATH DE number 2043365 (Why is no real title available?)
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Independent sets in graphs
• Constructing test functions for global optimization using continuous formulations of graph problems
• 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
• New results on the equivalence between zero-one programming and continuous concave programming
• Exact penalty functions for nonlinear integer programming problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5954199)