Dominating sets find application in a variety of networks. A subset of nodes D is a (1,2)-dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)-dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NP-hard. In this paper, we propose a polynomial time algorithm finding a minimal (1,2)-dominating set, Minimal_12_Set. We test the proposed algorithm in network models such as trees, geometric random graphs, random graphs and cubic graphs, and we show that the sets of nodes returned by the Minimal_12_Set are in general smaller than sets consisting of nodes chosen randomly.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.3390/electronics11030300
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach
- Language
- angielski
- Publication year
- 2022
