グラフの最小コストk分割について
スポンサーリンク
概要
- 論文の詳細を見る
グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.
- 1995-11-17
論文 | ランダム
- ペットとしてハムスターを飼育中に発症した気管支喘息患者の検討
- 富村水力発電所の緑化工事について (環境問題特集)
- 空気の水中噴射による貯水池結氷防止に関する実験的研究
- FOB,C&F,CIF契約とコンテナ・トレ-ド・タ-ムズ契約の危険移転時期の問題点--阪神大震災による神戸港コンテナ貨物の滅失・損傷との関連で
- 音響信号を利用したカーネル判別器による疲労紙幣検出 : Divergence-based カーネルを用いた時変スペクトル判別