Search
Abstract
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.
Citations
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.3390/electronics11030300
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
Electronics
no. 11,
ISSN: 2079-9292 - Language:
- English
- Publication year:
- 2022
- Bibliographic description:
- Raczek J.: Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks// Electronics -Vol. 11,iss. 3 (2022), s.300-
- DOI:
- Digital Object Identifier (open in new tab) 10.3390/electronics11030300
- Sources of funding:
-
- Free publication
- Verified by:
- Gdańsk University of Technology
seen 174 times
Recommended for you
On the super domination number of lexicographic product graphs
- M. Dettlaff,
- M. Lemańska,
- J. A. RODRíGUEZ-VELáZQUEZ
- + 1 authors