著者

山口 一章 増田 澄男

出版者

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

雑誌

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

巻号頁・発行日

vol.105, no.273, pp.39-42, 2005-09-08

---

頂点に重みがつけられた無向グラフが与えられたとき, 頂点の重みの和が最大となるクリークを求める問題は最大重みクリーク問題と呼ばれている.最大重みクリーク問題の厳密解を分枝限定法によって求める場合, 最大重みクリークの重みの, よりタイトな上界を高速に計算することが重要である.分枝限定法に基づく厳密解法の一つに, ある頂点系列により作成された有向グラフ上の最長経路を求め, それを上界計算に利用する方法がある.本稿は, より良い頂点系列を構成する方法を提案する.計算機実験により提案手法の有効性を検証する.