学術雑誌論文 Fast maximum weight clique extraction algorithm: Optimal tables for branch-and-bound

Shimizu, Satoshi  ,  Yamaguchi, Kazuaki  ,  Saitoh, Toshiki  ,  Masuda, Sumio

223pp.120 - 134 , 2017-05-31 , Elsevier B.V.
ISSN:0166218X18726771
内容記述
A new branch-and-bound algorithm for the maximum weight clique problem is proposed. The proposed algorithm consists of two phases, a precomputation phase and a branch and-bound phase. In the precomputation phase, the weights of maximum weight cliques in many small subgraphs are calculated and stored in optimal tables. In the branch and-bound phase, each problem is divided into smaller subproblems, and unnecessary subproblems are pruned using the optimal tables. We performed experiments with the proposed algorithm and five existing algorithms for several types of graphs. The results indicate that only the proposed algorithm can obtain exact solutions for all graphs and that it performs much faster than other algorithms for nearly all graphs.
本文を読む

http://www.lib.kobe-u.ac.jp/repository/90004069.pdf

このアイテムのアクセス数:  回

その他の情報