グラフの最小コストk分割について
スポンサーリンク
概要
- 論文の詳細を見る
グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.
- 1995-11-17
論文 | ランダム
- 1.企業文化は特許に現れるか(ワークショップ「知財の文化的側面」)
- P03(3) 開発競争における企業倫理(ワークショップ 企業倫理活動の現状と将来)
- 22・6・3 東京証券市場システム停止(22・6 工業社会の動向,22.技術と社会,機械工学年鑑)
- 22・6・1 建築強度偽造(22・6 工業社会の動向,22.技術と社会,機械工学年鑑)
- 22・6 工業社会の動向(22.技術と社会,機械工学年鑑)