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.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.3390/electronics11030300
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach
- Język
- angielski
- Rok wydania
- 2022
Źródło danych: MOSTWiedzy.pl - publikacja "Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks" link otwiera się w nowej karcie