1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Periodical Articles
  5. Item

Publications-Periodical Articles

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 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