Approximation for the minimum cost doubly resolving set problem

doi:10.1016/j.tcs.2015.03.048

CSpace > 应用数学研究所

	Approximation for the minimum cost doubly resolving set problem
	Chen, Xujin; Hu, Xiaodong; Wang, Changjun
	2016-01-04
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	609 页码:526-543
摘要	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.
关键词	Source location Doubly resolving set Approximation algorithms Polynomial-time solvability Metric dimension
DOI	10.1016/j.tcs.2015.03.048
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000367275000003
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/21628
专题	应用数学研究所
通讯作者	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.