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

DOI10.1007/S10107-014-0771-3zbMATH Open1309.90082OpenAlexW1971116373MaRDI QIDQ2340341FDOQ2340341

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

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

zbMATH Keywords

cutting planesclique numbersemidefinite bounds

Mathematics Subject Classification ID

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

Cites Work

• Maxima for Graphs and a New Proof of a Theorem of Turán
• Title not available (Why is that?)

Cited In (5)

• Title not available (Why is that?)
• Improved Bounds for Topological Cliques in Graphs of Large Girth
• Copositivity cuts for improving SDP bounds on the clique number
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• Strengthening Chvátal-Gomory cuts for the stable set problem

Uses Software

• CSDP
• YALMIP

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)