グラフの最小コスト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巻)
- コンストラクティヴィズムの視座と分析--規範の衝突・調整の実証的分析へ (規範と国際政治理論)
- 企業訪問レポート 活力ある中小企業探訪 品質を最優先する商品開発を目指す 株式会社大矢根利器製作所
- あたたかな防災イマジネーション・スパイラルの涵養(かんよう) (特集 災害を考える)
- 書評 通商摩擦研究の最新動向--構成主義アプローチと2レベルゲーム・モデル--大矢根聡著『日米韓半導体摩擦--通商交渉の政治経済学』有信堂、2002年 中戸祐夫著『日米通商摩擦の政治経済学』ミネルヴァ書房、2003年