期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 278, 期 1, 页码 76-90出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2019.03.047
关键词
Combinatorial optimization; Branch-and-bound; Maximum edge-weighted clique problem
资金
- Spanish Ministry of Science, Innovation and Universities through the project COGDRIVE [DPI2017-86915-C3-3-R]
We study the maximum edge-weighted clique problem, a problem related to the maximum (vertexweighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances. (C) 2019 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据