Approximation for the minimum cost doubly resolving set problem
文献类型：期刊论文
| 作者 | Chen, Xujin ; Hu, Xiaodong; Wang, Changjun
|
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2016-01-04 |
| 卷号 | 609页码:526-543 |
| 关键词 | Source location Doubly resolving set Approximation algorithms Polynomial-time solvability Metric dimension |
| ISSN号 | 0304-3975 |
| DOI | 10.1016/j.tcs.2015.03.048 |
| 英文摘要 | Locating source of diffusion in networks is crucial for controlling and preventing epidemic risks. It has been studied under various probabilistic models. In this paper, we study source location from a deterministic point of view by modeling it as the minimum cost doubly resolving set (DRS) problem, which is a strengthening of the well-known metric dimension problem. Let G be an undirected graph on n vertices, where each vertex has a nonnegative cost. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of vertices u, v in G, there exist x, y is an element of S such that the difference of distances (in terms of number of edges) between u and x, y is not equal to the difference of distances between v and x, y. The minimum cost DRS problem consists of finding a DRS in G with minimum total cost. We establish Theta(Inn) approximability of the minimum DRS problem on general graphs for both weighted and unweighted versions. This provides the first explicit lower and upper bounds on approximation for the minimum (cost) DRS, which are nearly tight. Moreover, we design the first known strongly polynomial time exact algorithms for the minimum cost DRS problem on general wheels and trees with additional constant k >= 0 edges. (C) 2015 Elsevier B.V. All rights reserved. |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000367275000003 |
| 出版者 | ELSEVIER SCIENCE BV |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/21627]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Wang, Changjun |
| 作者单位 | Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Chen, Xujin,Hu, Xiaodong,Wang, Changjun. Approximation for the minimum cost doubly resolving set problem[J]. THEORETICAL COMPUTER SCIENCE,2016,609:526-543. |
| APA | Chen, Xujin,Hu, Xiaodong,&Wang, Changjun.(2016).Approximation for the minimum cost doubly resolving set problem.THEORETICAL COMPUTER SCIENCE,609,526-543. |
| MLA | Chen, Xujin,et al."Approximation for the minimum cost doubly resolving set problem".THEORETICAL COMPUTER SCIENCE 609(2016):526-543. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。