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

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.

authors

• Butenko, Sergiy

published proceedings

• INFORMS JOURNAL ON COMPUTING

author list (cited authors)

• Hosseinian, S., Fontes, D., & Butenko, S.

citation count

• 2

complete list of authors

• Hosseinian, Seyedmohammadhossein||Fontes, Dalila BMM||Butenko, Sergiy

publication date

• January 2020

publisher

• Institute for Operations Research and the Management Sciences (INFORMS)  Publisher

published in

• INFORMS Journal on Computing  Journal

keywords

• Analytic Upper Bound On The Clique Number
• Graph Theory
• Maximum Edge Weight Clique Problem

Digital Object Identifier (DOI)

• 10.1287/ijoc.2019.0898

start page

• 747

end page

• 762

volume

• 32

issue

• 3

URL

• http://dx.doi.org/10.1287/ijoc.2019.0898