On the minimum differentially resolving set problem for diffusion source inference in networks

Chuan Zhou, Wei-Xue Lu, Peng Zhang, Jia Wu, Yue Hu, Li Guo

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

8 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAAAI 2016
Subtitle of host publicationProceedings of the 30th AAAI Conference on Artificial Intelligence
Place of PublicationPalo Alto, CA
PublisherAssociation for the Advancement of Artificial Intelligence
Pages79-85
Number of pages7
ISBN (Electronic)9781577357605
Publication statusPublished - 2016
Externally publishedYes
Event30th AAAI Conference on Artificial Intelligence, AAAI 2016 - Phoenix, United States
Duration: 12 Feb 201617 Feb 2016

Conference

Conference30th AAAI Conference on Artificial Intelligence, AAAI 2016
CountryUnited States
CityPhoenix
Period12/02/1617/02/16

Keywords

  • Differentially Resolving Set
  • Diffusion Source Inferenc
  • Networks

Fingerprint Dive into the research topics of 'On the minimum differentially resolving set problem for diffusion source inference in networks'. Together they form a unique fingerprint.

  • Cite this

    Zhou, C., Lu, W-X., Zhang, P., Wu, J., Hu, Y., & Guo, L. (2016). On the minimum differentially resolving set problem for diffusion source inference in networks. In AAAI 2016: Proceedings of the 30th AAAI Conference on Artificial Intelligence (pp. 79-85). Palo Alto, CA: Association for the Advancement of Artificial Intelligence.