A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem

DOI10.1287/ijoc.2019.0898zbMath1474.90494OpenAlexW3002616337WikidataQ126289413 ScholiaQ126289413MaRDI QIDQ3386795

Seyedmohammadhossein Hosseinian, Dalila B. M. M. Fontes, Sergiy I. Butenko

Publication date: 7 January 2021

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2019.0898

zbMATH Keywords

graph theorymaximum edge weight clique problemanalytic upper bound on the clique number

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Infra-chromatic bound for exact maximum clique search
• An exact bit-parallel algorithm for the maximum clique problem
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Solving the maximum edge weight clique problem via unconstrained quadratic programming
• An exact algorithm for the maximum clique problem
• A sequential elimination algorithm for computing bounds on the clique number of a graph
• Approximating the maximum vertex/edge weighted clique using local search
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Cliques and clustering: A combinatorial approach
• An extended formulation approach to the edge-weighted maximal clique problem
• A cutting-plane approach to the edge-weighted maximal clique problem
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• A fast algorithm for the maximum clique problem
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• Exact bounds on the order of the maximum clique of a graph.
• Energy minimization methods in computer vision and pattern recognition. 4th international workshop, EMMCVPR 2003, Lisbon, Portugal, July 7--9, 2003. Proceedings.
• Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
• Phased local search for the maximum clique problem
• A branch and bound algorithm for the maximum diversity problem
• Iterated tabu search for the maximum diversity problem
• Improvements to MCS algorithm for the maximum clique problem
• A review on algorithms for maximum clique problems
• Hybrid heuristics for the maximum diversity problem
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• On the Shannon capacity of a graph
• Reducibility among Combinatorial Problems
• The Eigenvalues of a Graph and Its Chromatic Number
• Upper Bounds on the Order of a Clique of a Graph
• Experimental and Efficient Algorithms
• Sur le coloriage des graphs
• A Lagrangian relaxation approach to the edge-weighted clique problem

This page was built for publication: A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem