Two Approaches to Constructing Certified Dominating Sets in Social Networks
Social networks are an important part of our community. In this context, certified dominating sets help to find in networks a group of people, referring as officials, such that 1) for each civilian, there is an official that can serve the civilian, and 2) no official is adjacent to exactly one civil...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10848090/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832542579570245632 |
|---|---|
| author | Joanna Raczek Mateusz Miotk |
| author_facet | Joanna Raczek Mateusz Miotk |
| author_sort | Joanna Raczek |
| collection | DOAJ |
| description | Social networks are an important part of our community. In this context, certified dominating sets help to find in networks a group of people, referring as officials, such that 1) for each civilian, there is an official that can serve the civilian, and 2) no official is adjacent to exactly one civilian, to prevent potential abuses. To delve deeper into this topic, this study considers two approaches to the problem of finding certified dominating sets of small cardinality. One approach is to transform an ordinary dominating set, which is subject only to condition 1) given above, into a certified dominating set. The second approach involves constructing such a set from scratch. To compare the two methods, we first studied the computational complexity of the decision problem of whether, for a given graph, the domination number, which is the minimum size of a dominating set, is equal to the certified domination number, that is, the minimum size of a certified dominating set. Next, we constructed and compared the performance of two approximate algorithms that find certified dominating sets, one for each of the two approaches. The effectiveness and efficiency of the proposed algorithms were validated through experiments that compare their results with each other and with a previous study: the linear-time algorithm, which determines the certified domination number for trees and with known results for the domination number in social networks. |
| format | Article |
| id | doaj-art-59f5f58b04324260b806ac3ef2fd1f40 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-59f5f58b04324260b806ac3ef2fd1f402025-02-04T00:00:48ZengIEEEIEEE Access2169-35362025-01-0113174951750510.1109/ACCESS.2025.353239210848090Two Approaches to Constructing Certified Dominating Sets in Social NetworksJoanna Raczek0https://orcid.org/0000-0002-1807-4978Mateusz Miotk1https://orcid.org/0000-0003-2768-7861Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Gdańsk, PolandFaculty of Mathematics, Physics and Informatics, University of Gdańsk, Gdańsk, PolandSocial networks are an important part of our community. In this context, certified dominating sets help to find in networks a group of people, referring as officials, such that 1) for each civilian, there is an official that can serve the civilian, and 2) no official is adjacent to exactly one civilian, to prevent potential abuses. To delve deeper into this topic, this study considers two approaches to the problem of finding certified dominating sets of small cardinality. One approach is to transform an ordinary dominating set, which is subject only to condition 1) given above, into a certified dominating set. The second approach involves constructing such a set from scratch. To compare the two methods, we first studied the computational complexity of the decision problem of whether, for a given graph, the domination number, which is the minimum size of a dominating set, is equal to the certified domination number, that is, the minimum size of a certified dominating set. Next, we constructed and compared the performance of two approximate algorithms that find certified dominating sets, one for each of the two approaches. The effectiveness and efficiency of the proposed algorithms were validated through experiments that compare their results with each other and with a previous study: the linear-time algorithm, which determines the certified domination number for trees and with known results for the domination number in social networks.https://ieeexplore.ieee.org/document/10848090/Algorithmic efficiencyapproximation algorithmscertified domination numbercomputational complexitydomination numbersafety |
| spellingShingle | Joanna Raczek Mateusz Miotk Two Approaches to Constructing Certified Dominating Sets in Social Networks IEEE Access Algorithmic efficiency approximation algorithms certified domination number computational complexity domination number safety |
| title | Two Approaches to Constructing Certified Dominating Sets in Social Networks |
| title_full | Two Approaches to Constructing Certified Dominating Sets in Social Networks |
| title_fullStr | Two Approaches to Constructing Certified Dominating Sets in Social Networks |
| title_full_unstemmed | Two Approaches to Constructing Certified Dominating Sets in Social Networks |
| title_short | Two Approaches to Constructing Certified Dominating Sets in Social Networks |
| title_sort | two approaches to constructing certified dominating sets in social networks |
| topic | Algorithmic efficiency approximation algorithms certified domination number computational complexity domination number safety |
| url | https://ieeexplore.ieee.org/document/10848090/ |
| work_keys_str_mv | AT joannaraczek twoapproachestoconstructingcertifieddominatingsetsinsocialnetworks AT mateuszmiotk twoapproachestoconstructingcertifieddominatingsetsinsocialnetworks |