| 講演抄録／キーワード |
| 講演名 |
2005-06-24 16:00
A Deterministic Algorithm for Finding All Minimum k-Way Cuts
○Yoko Kamidoi・Noriyoshi Yoshida（Hiroshima City Univ.）・Hiroshi Nagamochi（Kyoto Univ.） |
| 抄録 |
（和） |
$G=(V,E)$を節点数$n$, 枝数$m$の無向グラフとする．本稿では与えられた整数$k$に対する$G$の最小コスト$k$分割カットを求める決定的アルゴリズムを提案する．提案アルゴリズムは分割統治法であり，最小コスト$k$分割カット問題のひとつの問題例を最小コスト$(\lfloor (k+\sqrt{k})/2\rfloor+1)$ 分割カット問題の$O(n^{2k-5})$ 個の問題例に帰着する．アルゴリズムの時間計算量は$O(n^{4k/(1-1.71/\sqrt{k}) -31} )$ である．若干の変更を加えることにより提案アルゴリズムは時間で全ての最小コスト$k$分割を$O(n^{4k/(1-1.71/\sqrt{k}) -16} )$時間で求めることが可能になる． |
| （英） |
Let $G=(V,E)$ be an edge-weighted
undirected graph with $n$ vertices and $m$ edges.
We present a deterministic algorithm to compute
a minimum $k$-way cut of $G$ for a given $k$.
Our algorithm is a divide-and-conquer method
based on a procedure that reduces
an instance of the minimum $k$-way cut problem
to $O(n^{2k-5})$ instances
of the minimum $(\lfloor (k+\sqrt{k})/2\rfloor+1)$-way cut problem,
and can be implemented to run in
$O(n^{4k/(1-1.71/\sqrt{k}) -31} )$ time.
With a slight modification,
the algorithm can find all minimum $k$-way cuts in
$O(n^{4k/(1-1.71/\sqrt{k}) -16} )$ time. |
| キーワード |
（和） |
最小コストカット / 多分割カット / 分割統治法 / / / / / |
| （英） |
minimum cut / multiway cut / divide-and-conquer / / / / / |
| 文献情報 |
信学技報, vol. 105, no. 144, COMP2005-26, pp. 51-58, 2005年6月. |
| 資料番号 |
COMP2005-26 |
| 発行日 |
2005-06-17 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|