A characterization of the weighted Lovász number based on convex quadratic programming

DOI10.1007/S11590-015-0911-6MaRDI QIDQ5963688zbMATH OpenOpenAlexFDO

Authors Carlos J. Luz

Publication date 23 February 2016

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-015-0911-6

zbMATH Keywords

combinatorial optimizationgraph theorymaximum weight stable setquadratic programmingweighted Lovász number

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27)

Recommendations

• A characterization of the weighted version of McEliece-Rodemich-Rumsey-Schrijver number based on convex quadratic programming
• A Convex Quadratic Characterization of the Lovász Theta Number
• Spectral characterizations of the Lovász number and the Delsarte number of a graph
• scientific article; zbMATH DE number 2096432
• A quadratic programming approach to the determination of an upper bound on the weighted stability number

Cites work

• A Convex Quadratic Characterization of the Lovász Theta Number
• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• A quadratic programming approach to the determination of an upper bound on the weighted stability number
• A review on algorithms for maximum clique problems
• A simplex like approach based on star sets for recognizing convex-QP adverse graphs
• An upper bound on the independence number of a graph computable in polynomial-time
• Approximation of the stability number of a graph via copositive programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• Geometric algorithms and combinatorial optimization
• How the proof of the strong perfect graph conjecture was found
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• Lovász theta function, SVMs and finding dense subgraphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On the Shannon capacity of a graph
• Relaxations of vertex packing
• Solving semidefinite-quadratic-linear programs using SDPT3
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(5)

• Spectral characterizations of the Lovász number and the Delsarte number of a graph
• A characterization of the weighted version of McEliece-Rodemich-Rumsey-Schrijver number based on convex quadratic programming
• Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
• A survey on graphs with convex quadratic stability number
• A Convex Quadratic Characterization of the Lovász Theta Number

Describes a project that uses

Uses Software

• SDPT3
• DIMACS

This page was built for publication: A characterization of the weighted Lovász number based on convex quadratic programming

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