文献

J-GLOBAL ID：201802287447482899   整理番号：18A0168156

頂点Pk被覆問題に関する研究の総説【JST・京大機械翻訳】

A survey on vertex cover Pk problem

著者 (2件)： Wang Limin (南京大学計算机科学与技術系,南京,210023) ,  Hua Jingyu (南京大学計算机科学与技術系,南京,210023)
資料名： Nanjing Xinxi Gongcheng Daxue Xuebao  (Nanjing Xinxi Gongcheng Daxue Xuebao)
巻： 9  号： 5  ページ： 455-461  発行年： 2017年 
JST資料番号： C3600A  ISSN： 1674-7070  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： 頂点被覆問題は古典的NP完全問題であり,ランキング,計算機ネットワークなどの現実的な生活において多くの応用がある。ここ数年来、多くの研究者はその普及形式である頂点Pkカバー(VCPk)問題を探索し、即ち1つの頂点部分集合を発見し、トポロジー構造図から削除した後、残りの頂点から導出した部分グラフはPk路を含まない、その中のPkはk頂点を含む道である。本論文では、VCPk問題の応用背景を簡単に紹介し、近似アルゴリズム、正確なアルゴリズム、パラメータ化アルゴリズムの3つの方面における主な研究進展をまとめ、いくつかの主要な方法と技術を分析した。これに基づき、VCPk問題及び関連問題の研究の将来性について展望した。Data from Wanfang. Translated by JST【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  計算機網 ,  位相幾何学 ,  NP完全問題 ,  等級づけ ,  *文献展望 ,  部分グラフ ,  *被覆問題
準シソーラス用語： 近似アルゴリズム ,  頂点被覆 , 【Automatic Indexing@JST】

著者キーワード (4件)： vertex cover Pk ,  approximation algorithms ,  exact algorithms ,  parameter algorithms

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 頂点 ,  被覆問題 ,  研究 ,  総説