著者

上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.48, pp.17-22, 1995-11-17

参考文献数

5

---

グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.