文献

J-GLOBAL ID：201702243721603090   整理番号：17A0826262

単位ディスクグラフにおける集合を支配する構造高度にフォールトトレラント連結への新しい一定因子近似【Powered by NICT】

A New Constant Factor Approximation to Construct Highly Fault-Tolerant Connected Dominating Set in Unit Disk Graph

著者 (6件)： Wang Wei (School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China) ,  Liu Bei (School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China) ,  Kim Donghyun (Department of Computer Science, College of Computing and Software Engineering, Kennesaw State University, Marietta, GA, USA) ,  Li Deying (Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University), Ministry of Education School of Information, Renmin University of China, Beijing, China) ,  Wang Jingyi (School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China) ,  Gao Wei (School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China)
資料名： IEEE/ACM Transactions on Networking  (IEEE/ACM Transactions on Networking)
巻： 25  号： 1  ページ： 18-28  発行年： 2017年 
JST資料番号： W0507A  ISSN： 1063-6692  CODEN： IEANEP  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,よりa10年長いオープンNP困難問題のための新しい多項式時間定数因子近似アルゴリズムを提案し,最小四連結m-は文献で初めて単位円板グラフ(UDG)における集合問題を支配する任意の正整数m≧1であった。Tutte分解の構造制限,Wangらによって用いられている主要なグラフ理論ツールであるによるUDGにおける最小四接続m-支配集合問題を解くためのアルゴリズムを設計するために最小三接続m-支配集合問題のための既存の定数因子近似アルゴリズムを修正することは困難であることを観測した。この問題を解決するために,ここではまず,UDGにおける最小三接続m-支配集合問題のための新しい一定因子近似アルゴリズムを再発明と後にこのアルゴリズムを用いたUDGにおける最小四接続m-支配集合問題のための新しい一定因子近似アルゴリズムを設計した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： グラフ理論 ,  *フォールトトレランス ,  アルゴリズム ,  *近似法 ,  近似アルゴリズム
準シソーラス用語： 支配集合 ,  単位円板グラフ ,  多項式時間 ,  NP困難問題 , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (6件)： ディスク ,  グラフ ,  集合 ,  フォールトトレラント ,  因子 ,  近似