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-11
上傳時間 28-Apr-2020 13:50:21 (UTC+8)
摘要 In the problem of minimum connected dominating set with routing cost constraint, we are given a graph \\(G=(V,E)\\) and a positive integer \\(\\alpha \\), 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 \\cup \\{u,v\\}\\) is at most \\(\\alpha \\) times that in G. For general graphs, the only known previous approximability result is an \\(O(\\log n)\\)-approximation algorithm (\\(n=|V|\\)) for \\(\\alpha = 1\\) by Ding et al. For any constant \\(\\alpha > 1\\), we give an \\(O(n^{1-\\frac{1}{\\alpha }}(\\log n)^{\\frac{1}{\\alpha }})\\)-approximation algorithm. When \\(\\alpha \\ge 5\\), we give an \\(O(\\sqrt{n}\\log n)\\)-approximation algorithm. Finally, we prove that, when \\(\\alpha =2\\), unless \\(NP \\subseteq DTIME(n^{poly\\log n})\\), for any constant \\(\\epsilon > 0\\), the problem admits no polynomial-time \\(2^{\\log ^{1-\\epsilon }n}\\)-approximation algorithm, improving upon the \\(\\varOmega (\\log \\delta )\\) bound by Du et al., where \\(\\delta \\) is the maximum degree of G (albeit under a stronger hardness assumption).
關聯 Theoretical Computer Science, Vol.793, pp.140 - 151
資料類型 article
DOI https://doi.org/10.1016/j.tcs.2019.06.019
dc.contributor 資科系
dc.creator (作者) 郭桐惟
dc.creator (作者) Tung-Wei Kuo
dc.date (日期) 2019-11
dc.date.accessioned 28-Apr-2020 13:50:21 (UTC+8)-
dc.date.available 28-Apr-2020 13:50:21 (UTC+8)-
dc.date.issued (上傳時間) 28-Apr-2020 13:50:21 (UTC+8)-
dc.identifier.uri (URI) https://ah.lib.nccu.edu.tw/item?item_id=148384-
dc.description.abstract (摘要) In the problem of minimum connected dominating set with routing cost constraint, we are given a graph \\(G=(V,E)\\) and a positive integer \\(\\alpha \\), 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 \\cup \\{u,v\\}\\) is at most \\(\\alpha \\) times that in G. For general graphs, the only known previous approximability result is an \\(O(\\log n)\\)-approximation algorithm (\\(n=|V|\\)) for \\(\\alpha = 1\\) by Ding et al. For any constant \\(\\alpha > 1\\), we give an \\(O(n^{1-\\frac{1}{\\alpha }}(\\log n)^{\\frac{1}{\\alpha }})\\)-approximation algorithm. When \\(\\alpha \\ge 5\\), we give an \\(O(\\sqrt{n}\\log n)\\)-approximation algorithm. Finally, we prove that, when \\(\\alpha =2\\), unless \\(NP \\subseteq DTIME(n^{poly\\log n})\\), for any constant \\(\\epsilon > 0\\), the problem admits no polynomial-time \\(2^{\\log ^{1-\\epsilon }n}\\)-approximation algorithm, improving upon the \\(\\varOmega (\\log \\delta )\\) bound by Du et al., where \\(\\delta \\) is the maximum degree of G (albeit under a stronger hardness assumption).
dc.format.extent 2541917 bytes-
dc.format.mimetype application/pdf-
dc.relation (關聯) Theoretical Computer Science, Vol.793, pp.140 - 151
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 (資料類型) article
dc.identifier.doi (DOI) 10.1016/j.tcs.2019.06.019
dc.doi.uri (DOI) https://doi.org/10.1016/j.tcs.2019.06.019