On the Minimum Differentially Resolving Set Problem for Diffusion Source Inference in Networks

Chuan Zhou, Weixue Lu, Peng Zhang, Jia Wu, Yue Hu, Li Guo

AAAI 2016 pp. 79-86

doi:10.1609/AAAI.V30I1.10005 /aaai/2016/zhou2016aaai-minimum/

Abstract

In this paper we theoretically study the minimum Differentially Resolving Set (DRS) problem derived from the classical sensor placement optimization problem in network source locating. A DRS of a graph G = (V, E) is defined as a subset S ⊆ V where any two elements in V can be distinguished by their different differential characteristic sets defined on S. The minimum DRS problem aims to find a DRS S in the graph G with minimum total weight Σv∈S w(v). In this paper we establish a group of Integer Linear Programming (ILP) models as the solution. By the weighted set cover theory, we propose an approximation algorithm with the Θ(ln n) approximability for the minimum DRS problem on general graphs, where n is the graph size.

PDF AAAI Semantic Scholar

Cite

Text

Zhou et al. "On the Minimum Differentially Resolving Set Problem for Diffusion Source Inference in Networks." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10005

Markdown

[Zhou et al. "On the Minimum Differentially Resolving Set Problem for Diffusion Source Inference in Networks." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/zhou2016aaai-minimum/) doi:10.1609/AAAI.V30I1.10005

BibTeX

@inproceedings{zhou2016aaai-minimum,
  title     = {{On the Minimum Differentially Resolving Set Problem for Diffusion Source Inference in Networks}},
  author    = {Zhou, Chuan and Lu, Weixue and Zhang, Peng and Wu, Jia and Hu, Yue and Guo, Li},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {79-86},
  doi       = {10.1609/AAAI.V30I1.10005},
  url       = {https://mlanthology.org/aaai/2016/zhou2016aaai-minimum/}
}