Improving upper bounds for the clique number by non-valid inequalities

DOI10.1007/S10107-014-0771-3MaRDI QIDQ2340341zbMATH OpenOpenAlexFDO

Authors Marco Locatelli

Publication date 16 April 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-014-0771-3

zbMATH Keywords

clique numbercutting planessemidefinite bounds

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Programming involving graphs or networks (90C35)

Recommendations

• Copositivity cuts for improving SDP bounds on the clique number
• New analytical lower bounds on the clique number of a graph
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• Exact bounds on the order of the maximum clique of a graph.
• Improving an upper bound on the stability number of a graph

Cites work

• scientific article; zbMATH DE number 3634289 (Why is no real title available?)
• Maxima for Graphs and a New Proof of a Theorem of Turán

Cited in

(7)

• Copositivity cuts for improving SDP bounds on the clique number
• Strengthening Chvátal-Gomory cuts for the stable set problem
• scientific article; zbMATH DE number 7192822 (Why is no real title available?)
• Improved Bounds for Topological Cliques in Graphs of Large Girth
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems
• Application of the Lovász-Schrijver operator to compact stable set integer programs

Describes a project that uses

Uses Software

• YALMIP
• CSDP

This page was built for publication: Improving upper bounds for the clique number by non-valid inequalities

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