Approximability of the minimum weighted doubly resolving set problem

DOI10.1007/978-3-319-08783-2_31MaRDI QIDQ2920473zbMATH OpenOpenAlexFDO

Authors Changjun Wang, Xujin Chen

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4676

zbMATH Keywords

approximation algorithmsdoubly resolving setmetric dimensionpolynomial-time solvabilitysource location

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: 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,yinS$ 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 $Theta(lnn)$ 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 $kge0$ edges.

Recommendations

• Approximation for the minimum cost doubly resolving set problem
• Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs
• Computation of the double metric dimension in convex polytopes
• A novel approach for detecting multiple rumor sources in networks with partial observations
• Budgeted sensor placement for source localization on trees

Cited in

(16)

• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• Computation of the double metric dimension in convex polytopes
• A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
• Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs
• On doubly resolving sets in graphs
• The power of adaptivity in source identification with time queries on the path
• The equidistant dimension of graphs
• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• The \(k\)-metric dimension
• Budgeted sensor placement for source localization on trees
• A novel approach for detecting multiple rumor sources in networks with partial observations
• Computing edge version of metric and double metric dimensions of kayak paddle graphs
• Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs
• The doubly metric dimensions of cactus graphs and block graphs
• Approximation for the minimum cost doubly resolving set problem
• Extending the metric dimension to graphs with missing edges

This page was built for publication: Approximability of the minimum weighted doubly resolving set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920473)