グラフの最小コストk分割について
スポンサーリンク
概要
- 論文の詳細を見る
グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.
- 1995-11-17
論文 | ランダム
- 候補者の属性と投票行動-6-人間的魅力の計量的分析〔「都民の投票行動と政治意識-5-(選挙24巻6号)に続く〕
- 都民の投票行動と政治意識-5-年令・学歴・収入・職業のウエイト
- 都民の投票行動と政治意識--みのべ支持層とはたの支持層の特色-4-
- アメリカ人の投票行動と政治意識--カ州第34選挙区にみる有権者の動向-1-
- 都民の投票行動と政治意識--美濃部支持層と保守候補支持層の分析-3-