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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2020

Autores

Hosseinian, S (Autor) Outra; Dalila B.M.M. Fontes (Autor) FEP; Butenko, S (Autor) Outra

Revista

Título: INFORMS Journal on Computing

Vol. 32 Nº 3

Páginas: 747-762

ISSN: 1091-9856

Editora: Institute for Operations Research and the Management Sciences

Indexação

ISI Web of Knowledge - 6 Citações

Scopus

Outras Informações

ID Authenticus: P-00R-R6Z

DOI: 10.1287/ijoc.2019.0898

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 16