文献

J-GLOBAL ID：201602265830942031   整理番号：16A0858983

最大クリーク問題の重みは分割統治アルゴリズム【JST・京大機械翻訳】

Measure and conquer approach for maximum clique problem

著者 (5件)： Zhi Zhibing (School of Management, University of Shanghai for Science and Technology) ,  Ning Aibing (School of Management, University of Shanghai for Science and Technology) ,  Chen Jizhen (School of Management, University of Shanghai for Science and Technology) ,  Wang Yongfei (School of Management, University of Shanghai for Science and Technology) ,  Yang Xiaofang (School of Management, University of Shanghai for Science and Technology)
資料名： Jisuanji Gongcheng yu Yingyong  (Jisuanji Gongcheng yu Yingyong)
巻： 52  号： 2  ページ： 50-53  発行年： 2016年 
JST資料番号： C2533A  ISSN： 1002-8331  CODEN： JGYYAT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： 分岐次数は現在広く組合せ最適化の分野における難題を解くための技術の一つであり,この技術の核心は,いくつかのサブ問題として原問題の分岐である,そして再帰的これらのサブ問題を解く。加重分割統治技術はアルゴリズムの設計と時間複雑性を分析する中の1つの新しい技術である。最大クリーク問題を解くことが1つの分岐次数に基づく再帰的アルゴリズムを設計した。問題の規模の数Nの多項式関数を,その中にはP(N)は,通常の技術を用いてこのアルゴリズムに対する時間複雑性解析を行い,その時間の複雑性がO(1.380~NP(N))であることを表した。加重分割統治技術を用いてアルゴリズムに対する時間複雑性解析を行い,このアルゴリズムの時間の複雑性は元のO(1.380~NP(N))からO(1.325~NP(N))に低下した。研究結果は,加重分割統治技術を用いて比較的正確な時間の複雑性を得ることができることを示す。Data from the ScienceChina, LCAS.【JST・京大機械翻訳】

シソーラス用語： *分割統治法 ,  多項式 ,  *アルゴリズム ,  最適化
準シソーラス用語： 再帰アルゴリズム ,  複雑性 ,  アルゴリズム設計 ,  *ガバナンス ,  加重 ,  次数 ,  *最大クリーク問題 , 【Automatic Indexing@JST】

著者キーワード (4件)： branch and reduce ,  maximum clique problem ,  measure and conquer ,  algorithm complexity

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 最大クリーク問題 ,  分割統治アルゴリズム