1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Periodical Articles
  5. Item

學術產出-Periodical Articles

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

題名 On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint
作者 郭桐惟
Tung-Wei Kuo
貢獻者 資科系
關鍵詞 Connected dominating set ;  Spanner ;  Set cover with pairs ;  MIN-REP problem 
日期 2019-02
上傳時間 28-Apr-2020 13:50:37 (UTC+8)
摘要 In the problem of minimum connected dominating set with routing cost constraint, we are given a graph G=(V,E)G=(V,E) and a positive integer αα, and the goal is to find the smallest connected dominating set D of G such that, for any two non-adjacent vertices u and v in G, the number of internal nodes on the shortest path between u and v in the subgraph of G induced by D∪{u,v}D∪{u,v} is at most αα times that in G. For general graphs, the only known previous approximability result is an O(logn)O(log⁡n)-approximation algorithm (n=|V|n=|V|) for α=1α=1 by Ding et al. For any constant α>1α>1, we give an O(n1−1α(logn)1α)O(n1−1α(log⁡n)1α)-approximation algorithm. When α≥5α≥5, we give an O(n−−√logn)O(nlog⁡n)-approximation algorithm. Finally, we prove that, when α=2α=2, unless NP⊆DTIME(npolylogn)NP⊆DTIME(npolylog⁡n), for any constant ϵ>0ϵ>0, the problem admits no polynomial-time 2log1−ϵn2log1−ϵ⁡n-approximation algorithm, improving upon the Ω(logδ)Ω(log⁡δ) bound by Du et al., where δδ is the maximum degree of G (albeit under a stronger hardness assumption).
關聯 International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2018: Algorithms for Sensor Systems pp 32-46
資料類型 conference
DOI https://doi.org/10.1007/978-3-030-14094-6_3
dc.contributor 資科系
dc.creator (作者) 郭桐惟
dc.creator (作者) Tung-Wei Kuo
dc.date (日期) 2019-02
dc.date.accessioned 28-Apr-2020 13:50:37 (UTC+8)-
dc.date.available 28-Apr-2020 13:50:37 (UTC+8)-
dc.date.issued (上傳時間) 28-Apr-2020 13:50:37 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/129539-
dc.description.abstract (摘要) In the problem of minimum connected dominating set with routing cost constraint, we are given a graph G=(V,E)G=(V,E) and a positive integer αα, and the goal is to find the smallest connected dominating set D of G such that, for any two non-adjacent vertices u and v in G, the number of internal nodes on the shortest path between u and v in the subgraph of G induced by D∪{u,v}D∪{u,v} is at most αα times that in G. For general graphs, the only known previous approximability result is an O(logn)O(log⁡n)-approximation algorithm (n=|V|n=|V|) for α=1α=1 by Ding et al. For any constant α>1α>1, we give an O(n1−1α(logn)1α)O(n1−1α(log⁡n)1α)-approximation algorithm. When α≥5α≥5, we give an O(n−−√logn)O(nlog⁡n)-approximation algorithm. Finally, we prove that, when α=2α=2, unless NP⊆DTIME(npolylogn)NP⊆DTIME(npolylog⁡n), for any constant ϵ>0ϵ>0, the problem admits no polynomial-time 2log1−ϵn2log1−ϵ⁡n-approximation algorithm, improving upon the Ω(logδ)Ω(log⁡δ) bound by Du et al., where δδ is the maximum degree of G (albeit under a stronger hardness assumption).
dc.format.extent 522765 bytes-
dc.format.mimetype application/pdf-
dc.relation (關聯) International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2018: Algorithms for Sensor Systems pp 32-46
dc.subject (關鍵詞) Connected dominating set ;  Spanner ;  Set cover with pairs ;  MIN-REP problem 
dc.title (題名) On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint
dc.type (資料類型) conference
dc.identifier.doi (DOI) 10.1007/978-3-030-14094-6_3
dc.doi.uri (DOI) https://doi.org/10.1007/978-3-030-14094-6_3