A Fast Exact Algorithm for Deployment of Sensor Nodes for Internet of Things

Qinghua Zheng, Chutong Yang, Haijun Yang () and Jianhe Zhou
Additional contact information
Qinghua Zheng: Guangxi University of Science and Technology
Chutong Yang: University of California San Diego
Haijun Yang: Beihang University
Jianhe Zhou: Guangxi University of Science and Technology

Information Systems Frontiers, 2020, vol. 22, issue 4, No 4, 829-842

Abstract: Abstract The deployment problem of sensor nodes of Internet of things (IoT) can be abstracted as listing minimal dominating sets of a graph. The problem of listing all the minimal dominating sets in a graph can be converted to the problem of state space search among candidate vertex sets. The search and optimization technologies, such as the bidirectional search and branch cut, can be applied to solve the problem effectively. Our experiments show that the new algorithm can reduce the running time by at least an order of magnitude, compared to a state-of-the-art algorithm for listing all the minimal dominating sets.

Keywords: Graph; Minimal dominating set; Exact algorithm; State space search (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10796-018-9890-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:infosf:v:22:y:2020:i:4:d:10.1007_s10796-018-9890-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10796

DOI: 10.1007/s10796-018-9890-3

Access Statistics for this article

Information Systems Frontiers is currently edited by Ram Ramesh and Raghav Rao

More articles in Information Systems Frontiers from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().