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

Seyedmohammadhossein Hosseinian (), Dalila B. M. M. Fontes () and Sergiy Butenko ()
Additional contact information
Seyedmohammadhossein Hosseinian: Industrial & Systems Engineering, Texas A&M University, College Station, Texas 77843
Dalila B. M. M. Fontes: Institute for Systems and Computer Engineering, Technology and Science and Faculdade de Economia, Universidade do Porto, 4200-465 Porto, Portugal
Sergiy Butenko: Industrial & Systems Engineering, Texas A&M University, College Station, Texas 77843

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 747-762

Abstract: This paper explores the connections between the classical maximum clique problem and its edge-weighted generalization, the maximum edge weight clique (MEWC) problem. As a result, a new analytic upper bound on the clique number of a graph is obtained and an exact algorithm for solving the MEWC problem is developed. The bound on the clique number is derived using a Lagrangian relaxation of an integer (linear) programming formulation of the MEWC problem. Furthermore, coloring-based bounds on the clique number are used in a novel upper-bounding scheme for the MEWC problem. This scheme is employed within a combinatorial branch-and-bound framework, yielding an exact algorithm for the MEWC problem. Results of computational experiments demonstrate a superior performance of the proposed algorithm compared with existing approaches.

Keywords: graph theory; analytic upper bound on the clique number; maximum edge weight clique problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0898 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:3:i:2020:p:747-762

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().