最小 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
論文 | ランダム
- 216 木造軸組建物における剛床仮定の成立する床剛性(構造)
- 209 有限正弦波による完全弾塑性1質点系の最大変位応答予測(構造)
- 208 アーチ構造における損傷制御設計の適用に関する研究 その2(構造)
- Heat Transfer in Meat Patties during Double-Sided Cooking
- The Flavor Symmetry