期刊
INFORMS JOURNAL ON COMPUTING
卷 32, 期 3, 页码 747-762出版社
INFORMS
DOI: 10.1287/ijoc.2019.0898
关键词
graph theory; analytic upper bound on the clique number; maximum edge weight clique problem
资金
- National Science Foundation [CMMI-1538493]
- Office of Naval Research [N00014-13-1-0635]
- Portuguese Foundation for Science and Technology [POCI-01-0145-FEDER-031821]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据