2014/04/18 by Xujin Chen, Chen, Xujin, Xiaodong Hu +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1404.4676
arxiv created 2014/04/18 · openalex publication_date 2014/04/18 · arxiv updated 2014/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 weighted doubly resolving set (DRS) problem, which is a strengthening of the well-known metric dimension problem. Let G be a vertex weighted undirected graph on n vertices. A vertex subset S of G is DRS of G if for every pair of vertices u,v in G, there exist x,y∈ 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 weighted DRS problem consists of finding a DRS in G with minimum total weight. We establish Θ(ln n) approximability of the minimum DRS problem on general graphs for both weighted and unweighted versions. This is the first work providing explicit approximation lower and upper bounds for minimum (weighted) DRS problem, which are nearly tight. Moreover, we design first known strongly polynomial time algorithms for the minimum weighted DRS problem on general wheels and trees with additional constant k≥0 edges.