On characterization of maximal independent sets via quadratic optimization

DOI10.1007/s10732-011-9171-5zbMath1365.90186OpenAlexW1970740332MaRDI QIDQ2359154

Foad Mahdavi Pajouh, Balabhaskar Balasundaram, Oleg A. Prokopyev

Publication date: 27 June 2017

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-011-9171-5

zbMATH Keywords

independence numberquadratic optimizationlocal maxima

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Quadratic programming (90C20)

Related Items (4)

Solving the maximum vertex weight clique problem via binary quadratic programming ⋮ The unconstrained binary quadratic programming problem: a survey ⋮ On optimization problems in acyclic hypergraphs ⋮ Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

Uses Software

• DIMACS
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diversification-driven tabu search for unconstrained binary quadratic problems
• Pseudo-Boolean optimization
• Multistart tabu search strategies for the unconstrained binary quadratic optimization problem
• An unconstrained quadratic binary programming approach to the vertex coloring problem
• Experiments in quadratic 0-1 programming
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• The maximum clique problem
• Evolution towards the maximum clique
• Variable neighborhood search
• Ellipsoidal approach to box-constrained quadratic problems
• Global optimality conditions for quadratic \(0-1\) optimization problems
• On a polynomial fractional formulation for independence number of a graph
• Lower bound improvement and forcing rule for quadratic binary programming
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Global Optimality Conditions for Quadratic Optimization Problems with Binary Constraints
• Some news about the independence number of a graph
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Global equilibrium search applied to the unconstrained binary quadratic optimization problem
• Constructing test functions for global optimization using continuous formulations of graph problems
• Variable neighborhood search: Principles and applications
• Finding independent sets in a graph using continuous multivariable polynomial formulations.

This page was built for publication: On characterization of maximal independent sets via quadratic optimization