A Branch-and-Bound Based Exact Algorithm for the Maximum Edge-Weight Clique Problem
| Autor: | Sumio Masuda, Kazuaki Yamaguchi, Satoshi Shimizu |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Clique
021103 operations research Branch and bound 0211 other engineering and technologies 02 engineering and technology Combinatorics Exact algorithm Clique problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Enhanced Data Rates for GSM Evolution Undirected graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Computational Science/Intelligence & Applied Informatics ISBN: 9783319968056 CSII (selected papers) |
| DOI: | 10.1007/978-3-319-96806-3_3 |
| Popis: | The maximum edge-weight clique problem is to find a clique whose sum of edge-weight is maximum for a given edge-weighted undirected graph. The problem is NP-hard and was formulated as a mathematical programming problem in previous studies. In this paper, we propose an exact algorithm based on branch-and-bound. By some computational experiments, we confirmed our proposal algorithm is faster than the methods based on mathematical programming. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|