Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
Dominating sets find application in a variety of networks. A subset of nodes <i>D</i> is a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-01-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/11/3/300 |
| _version_ | 1797488399154675712 |
|---|---|
| author | Joanna Raczek |
| author_facet | Joanna Raczek |
| author_sort | Joanna Raczek |
| collection | DOAJ |
| description | Dominating sets find application in a variety of networks. A subset of nodes <i>D</i> is a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-dominating set in a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> if every node not in <i>D</i> is adjacent to a node in <i>D</i> and is also at most a distance of 2 to another node from <i>D</i>. In networks, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-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. |
| first_indexed | 2024-03-10T00:02:35Z |
| format | Article |
| id | doaj.art-ac25be8eb5324a208a8c43a37694efc3 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T00:02:35Z |
| publishDate | 2022-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-ac25be8eb5324a208a8c43a37694efc32023-11-23T16:14:40ZengMDPI AGElectronics2079-92922022-01-0111330010.3390/electronics11030300Polynomial Algorithm for Minimal (1,2)-Dominating Set in NetworksJoanna Raczek0Department of Algorithms and Systems Modelling, Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, PolandDominating sets find application in a variety of networks. A subset of nodes <i>D</i> is a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-dominating set in a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> if every node not in <i>D</i> is adjacent to a node in <i>D</i> and is also at most a distance of 2 to another node from <i>D</i>. In networks, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula>-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.https://www.mdpi.com/2079-9292/11/3/300computational complexityalgorithmsdomination number(1,2)-domination numbernetworks |
| spellingShingle | Joanna Raczek Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks Electronics computational complexity algorithms domination number (1,2)-domination number networks |
| title | Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks |
| title_full | Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks |
| title_fullStr | Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks |
| title_full_unstemmed | Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks |
| title_short | Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks |
| title_sort | polynomial algorithm for minimal 1 2 dominating set in networks |
| topic | computational complexity algorithms domination number (1,2)-domination number networks |
| url | https://www.mdpi.com/2079-9292/11/3/300 |
| work_keys_str_mv | AT joannaraczek polynomialalgorithmforminimal12dominatingsetinnetworks |