グラフの最小コストk分割について
スポンサーリンク
概要
- 論文の詳細を見る
グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.
- 1995-11-17
論文 | ランダム
- 眼窩隔膜を利用した眼瞼下垂症手術 (特集 眼瞼の退行性疾患に対する眼形成外科手術) -- (上眼瞼の退行性(加齢性)疾患)
- 挙筋腱膜(levator aponeurosis)の利用を主体とした眼瞼下垂症手術 (特集 眼瞼の退行性疾患に対する眼形成外科手術) -- (上眼瞼の退行性(加齢性)疾患)
- 4県におけるマンボウ類の漁獲状況
- 日本周辺におけるマンボウ類に関するアンケート調査結果
- 鹿児島湾産ワキヤハタの年齢と成長,およびオオメハタとの比較(短報)