著者

山口 一章 増田 澄男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.7, pp.1-4, 2005-04-11

---

頂点に重みが付けられた無向グラフが与えられたときに最大重みクリークを求めよという最適化問題は最大重みクリーク問題と呼ばれている. 最大重みクリーク問題の解法としては分枝限定法によるものが知られている. 分枝限定法において計算時間を短縮するためには, タイトな上界をできるだけ短い時間で計算することが重要である. 本稿では, 高速かつ単純な最大重みクリークの上界計算法を提案し, その有効性を実験的に検証する.