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

Zhou, C; Lu, WX; Zhang, P; Wu, J; Hu, Y; Guo, L

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

Zhou, C Lu, WX Zhang, P

Wu, J Hu, Y Guo, L

Permalink

Publication Type:: Conference Proceeding
Citation:: 30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2016, pp. 79 - 85
Issue Date:: 2016-01-01

Closed Access

	Filename	Description	Size
	Minimum.pdf	Published version	689.54 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhou, C	en_US
dc.contributor.author	Lu, WX	en_US
dc.contributor.author	Zhang, P https://orcid.org/0000-0001-7973-2746	en_US
dc.contributor.author	Wu, J	en_US
dc.contributor.author	Hu, Y	en_US
dc.contributor.author	Guo, L	en_US
dc.date.issued	2016-01-01	en_US
dc.identifier.citation	30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2016, pp. 79 - 85	en_US
dc.identifier.isbn	9781577357605	en_US
dc.identifier.uri	http://hdl.handle.net/10453/106120
dc.description.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.	en_US
dc.relation.ispartof	30th AAAI Conference on Artificial Intelligence, AAAI 2016	en_US
dc.title	On the minimum differentially resolving set problem for diffusion source inference in networks	en_US
dc.type	Conference Proceeding
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/106120