Wyszukiwarka
Abstrakt
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.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.3390/electronics11030300
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
Electronics
nr 11,
ISSN: 2079-9292 - Język:
- angielski
- Rok wydania:
- 2022
- Opis bibliograficzny:
- Raczek J.: Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks// Electronics -Vol. 11,iss. 3 (2022), s.300-
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.3390/electronics11030300
- Źródła finansowania:
-
- Publikacja bezkosztowa
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 174 razy
Publikacje, które mogą cię zainteresować
On the super domination number of lexicographic product graphs
- M. Dettlaff,
- M. Lemańska,
- J. A. RODRíGUEZ-VELáZQUEZ
- + 1 autorów