最小カット問題の新しい確率的アルゴリズム：計算実験による性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 1992-03-23
• タイトル: 最小カット問題の新しい確率的アルゴリズム：計算実験による性能評価
• タイトル / 言語: en
• タイトル: A New Randomized Algorithm for the Minimum Cut Problem and Its Performance Evaluation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神戸商科大学管理科学科
• 著者所属: 神戸商科大学管理科学科
• 著者所属: 神戸商科大学管理科学科
• 著者所属: 日本IBM東京基礎研究所
• 著者所属(英): en
• 著者所属(英): Department of Management Science, Kobe University of Commerce
• 著者所属(英): en
• 著者所属(英): Department of Management Science, Kobe University of Commerce
• 著者所属(英): en
• 著者所属(英): Department of Management Science, Kobe University of Commerce
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan
• 著者名: 大塚啓司; 戴陽; 加藤, 直樹; 岩野, 和生
• 著者名(英): Keisi, Ohtsuka; Yang, Dai; Naoki, Katoh; Kazuo, Iwano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: G=（，）をn個の節点とm本の枝からなる連結な無向グラフとするとき、Gの初等的カットのなかで枝数最小のカット（最小カット）を求める確率的アルゴリズムを提案し、その性能を計算機実験で評価する。アルゴリズムは最大格差最小カットを求める高速解法にもとずくもので、その理論的評価は未解決であるが、計算機実験の結果、最小カットを求める厳密解法と比較すると少ない計算量で最小カットに近いカットが求められることが確かめられた。また同様の手法をGを等分割する最小カットを求める問題（グラフの2分割問題）に対しても開発し、その性能を従来の Kernighan and Lin による近似解法と比較実験した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let G=(V,E) be a connected undirected graph with n vertices and m. We shall propose a new randomized algorithm for finding a minimum cut based on a fast algorithm for finding a minimum range cut. Though the theoretical evaluation has not been done yet, computer experiments show that our algorithm outputs a cut very close to the exact minimum cut with the running time shorter than the best known algorithm for the minimum cut problem. We also propose a randomized algorithm based on the similar idea for finding a minimum cut of G into equal sizes. We also report the results of computer experiments that compare our algorithm with Kernighan and Lin's algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1992, 号 27(1991-AL-026), p. 17-24, 発行日 1992-03-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会