最小 3-カット, 4-カットを計算するアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
k=3,4に対し, 重み付きグラフの最小 k-カットを求めるO(n^<k-2>(nF(n, m) + C_2(n, m)+n^2)) = O(mn^klog(n^2/m))時間アルゴリズムを与える. ここで、n, mはグラフの点数, 辺数であり, F(n, m)とC_2(n, m)はそれぞれ n 点、m 辺グラフ上での最大流, 最小2-カットを求める時間である. このアルゴリズムを拡張させて, 対称な劣モジュラシステムにおける最小3-カットを効率良く計算することもできる.
- 1999-01-27
論文 | ランダム
- 13p-PS-17 NbS_の超伝導
- 30p-M-8 HfTe_5抵抗異常 [IV]
- 日本と中国における文人庭園の変遷と特徴 (平成20年度日本庭園学会全国大会研究発表要旨)
- 長野県松代町に見られる水路網と庭園群の特徴 (平成20年度日本庭園学会全国大会研究発表要旨)
- 平成20年度日本庭園学会全国大会研究発表要旨