著者

浅田 信浩 増田 澄男 山口 一章

出版者

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

雑誌

電子情報通信学会総合大会講演論文集

巻号頁・発行日

vol.2005, no.1, 2005-03-07

著者

山口 一章 増田 澄男

出版者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

山口 一章 増田 澄男

出版者

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

雑誌

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

巻号頁・発行日

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

---

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