A more efficient algorithm for finding a maximum clique with an improved approximate coloring (数理モデル化と問題解決)

スポンサーリンク

概要

• 論文の詳細を見る

• We propose a new, practical, and exact algorithm for finding a maximum clique in a graph. The algorithm is a considerably improved version of the MCR algorithm, which is a very efficient branch-and-bound algorithm. The improvement is achieved by devising a sophisticated procedure for approximate coloring as well as by introducing a novel strategy for ordering vertices in the branch-and bound procedure. It is experimentally demonstrated that the new algorithm is remarkably faster than MCR and other existing algorithms for most benchmark instances.

• 一般社団法人情報処理学会の論文
• 2007-06-25

著者

• TOMITA Etsuji

  Department of Information and Communication Engineering, and The Advanced Algorithms Research Labora

• Tomita Etsuji

  Department Of Information And Communication Engineering The University Of Electro-communications

• Tomita Etsuji

  Department Of Information And Communication Engineering And The Advanced Algorithms Research Laborat

• Sutani Yoichi

  Department of Information and Communication Engineering The University of Electro-Communications

• Higashi Takanori

  Department of Information and Communication Engineering The University of Electro-Communications

関連論文

• The maximum clique problem and its applications (数理モデル化と問題解決 バイオ情報学)
• A more efficient algorithm for finding a maximum clique with an improved approximate coloring (数理モデル化と問題解決)
• The Maximum Clique Problem and Its Applications
• NetMCQ : A Distributed Exact Maximum Clique Solver
• NetMCQ: a distributed exact maximum clique solver (数理モデル化と問題解決 バイオ情報学)

スポンサーリンク