グラフ最小コスト3分割アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1994-03-17
• タイトル: グラフ最小コスト3分割アルゴリズム
• タイトル / 言語: en
• タイトル: An Algorithm for Finding a Minimum Three - Way Cut of a Graph
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学工学部
• 著者所属: 広島大学工学部
• 著者所属: 広島大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者名: 上土井陽子; 若林, 真一; 吉田, 典可
• 著者名(英): Yoko, Kamidoi; Shin-Ichi, Wakabayashi; Noriyoshi, Yoshida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 枝に正の重みを持つグラフGとk個の異なる節点が与えられたとき，k個の節点を互いに非連結にする最小コストのk分割カットを求める問題を最小コストk分割問題とする．k≧3の場合，最小コストk分割問題は一般のグラフにおいては全ての節点次数を3以下と制約してもNP困難であることが知られている．一方，平面グラフに対してはkが定数の場合に対し，多項式時間最小コストk分割アルゴリズムが提案されている．本稿では平面グラフより広いクラスに属するグラフに対し，最小コスト3分割問題を考察する．はじめにグラフで最小コスト2分割カット，最小コスト3分割カットの性質を導出する．次に，導出した性質に基づき，平面グラフより広いクラスに属するグラフに対してO（^dm log（^2/））の計算時間で最小コスト3分割を求めるアルゴリズムを提案する．ここで，dはGの最大節点次数と次数3以上の節点数により上限が与えられる値である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a graph G with n vertices, m edges and positive edge weights and k distinct terminals {s_1,s_2,…,s_k} on G, problem of computing a minimum k-way cut of G s to find minimum (cost) k-way cut G that disconnects each terminal from all the others. The minimum k-way cut problem for a general graph and a fixed integer k(〓3) is known as NP-hard, and the problem for a graph and a fixed integer k can be solved in polynomial time. The complexity of this problem for any other class that is larger than planar graphs and smaller than general graphs was not known. This paper presents an algorithm for computing a minimum three-way cut of a graph in a larger class than the class of planar graphs. Our algorithm constructs a minimum three-way cut of a graph in time O(n^dm log(n^2/m)), where d is bounded by the maximum vertex degree and the number of vertices whose degree is more than two.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 26(1993-AL-038), p. 1-8, 発行日 1994-03-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会