文献

J-GLOBAL ID：201102241593503485   整理番号：11A1280431

マルチカット問題の改良パラメータ化されたアルゴリズム

Improved Parameterized Algorithm for the Multicut Problem

著者 (3件)： Liu Yunlong (School of Information Sci. and Engineering, Central South Univ., Changsha) ,  Wang Jianxin (School of Information Sci. and Engineering, Central South Univ., Changsha) ,  Chen Jianer (School of Information Sci. and Engineering, Central South Univ., Changsha)
資料名： Ruanjian Xuebao  (Ruanjian Xuebao)
巻： 21  号： 7  ページ： 1515-1523  発行年： 2010年 
JST資料番号： C2542A  ISSN： 1000-9825  CODEN： RUXUEW  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： マルチカット問題は最小頂点セットを見つけるために与えられたグラフと端子対の収集で,どの対の二端子もこの頂点セット削除後に結合しない。この問題はNP完全問題である。その構造特性の深い分析に基き,設定分割戦略と別の関連問題の改善結果を用いて,本紙はこの問題の実行時間O*のパラメタ化アルゴリズムを提示する。この場合,1は端子対数を意味しkは除去した頂点の数を意味する。このアルゴリズムは走行時間O*の前の物を著しく改善する。Data from the ScienceChina, LCAS. Translated by JST

シソーラス用語： *アルゴリズム ,  *パラメタリゼーション ,  マルチ ,  NP完全問題 ,  走行時間 ,  パラメータ ,  構造特性 ,  グラフ
準シソーラス用語： *パラメータ化

分類 (1件)： 計算機網  (JC03000K)

タイトルに関連する用語 (4件)： マルチ ,  問題 ,  パラメータ ,  アルゴリズム