講演抄録/キーワード |
講演名 |
2005-04-18 10:00
最大重みクリークの重みの上界の高速な計算法 ○山口一章・増田澄男(神戸大) |
抄録 |
(和) |
頂点に重みが付けられた無向グラフが与えられたときに最大重みクリークを求
めよという最適化問題は最大重みクリーク問題と呼ばれている.最大重みクリー
ク問題の解法としては分枝限定法によるものが知られている.分枝限定法にお
いて計算時間を短縮するためには,タイトな上界をできるだけ短い時間で計算
することが重要である.本稿では,高速かつ単純な最大重みクリークの上界計
算法を提案し,その有効性を実験的に検証する. |
(英) |
We deal with the optimization problem that requies the maximum weighted
clique of undirected graphs. Some exact algorithms based on the
branch-and-bound method have been proposed. The computation time
strongly depends on the tightness of upper bounds and the computation
time of calculating upper bounds. In this paper we show a fast and
simple algorithm for calculating upper bounds. We also show the
effictiveness by some computational experiments. |
キーワード |
(和) |
クリーク / 分枝限定法 / 頂点彩色 / 最長路 / / / / |
(英) |
clique / branch and bound / vertex coloring / longest path / / / / |
文献情報 |
信学技報, vol. 105, no. 7, COMP2005-1, pp. 1-4, 2005年4月. |
資料番号 |
COMP2005-1 |
発行日 |
2005-04-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|