NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3
In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or (k + 1) vertices correspondingly. The linked e...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2021-03-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1470 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849338833468915712 |
|---|---|
| author | Alexander Valeryevich Smirnov |
| author_facet | Alexander Valeryevich Smirnov |
| author_sort | Alexander Valeryevich Smirnov |
| collection | DOAJ |
| description | In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or (k + 1) vertices correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of k linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. A multiple tree is a connected multiple graph with no cycles. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. The problem of finding the spanning tree can be set for a multiple graph. Complete spanning trees form a special class of spanning trees of a multiple graph. Their peculiarity is that a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. Also we can formulate the problems of recognition of the spanning tree and complete spanning tree of the limited weight. The main result of this article is the proof of NPcompleteness of such recognition problems for arbitrary multiple graphs as well as for divisible multiple graphs in the case when multiplicity k ≥ 3. The corresponding optimization problems are NP-hard. |
| format | Article |
| id | doaj-art-7faba79f67e647d5b05bdc9286570cb4 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2021-03-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-7faba79f67e647d5b05bdc9286570cb42025-08-20T03:44:17ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172021-03-01281223710.18255/1818-1015-2021-1-22-371120NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3Alexander Valeryevich Smirnov0P. G. Demidov Yaroslavl State UniversityIn this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or (k + 1) vertices correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of k linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. A multiple tree is a connected multiple graph with no cycles. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. The problem of finding the spanning tree can be set for a multiple graph. Complete spanning trees form a special class of spanning trees of a multiple graph. Their peculiarity is that a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. Also we can formulate the problems of recognition of the spanning tree and complete spanning tree of the limited weight. The main result of this article is the proof of NPcompleteness of such recognition problems for arbitrary multiple graphs as well as for divisible multiple graphs in the case when multiplicity k ≥ 3. The corresponding optimization problems are NP-hard.https://www.mais-journal.ru/jour/article/view/1470multiple graphmultiple treedivisible graphspanning treecomplete spanning treeminimum spanning treenp-completeness |
| spellingShingle | Alexander Valeryevich Smirnov NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3 Моделирование и анализ информационных систем multiple graph multiple tree divisible graph spanning tree complete spanning tree minimum spanning tree np-completeness |
| title | NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3 |
| title_full | NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3 |
| title_fullStr | NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3 |
| title_full_unstemmed | NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3 |
| title_short | NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3 |
| title_sort | np completeness of the minimum spanning tree problem of a multiple graph of multiplicity k ≥ 3 |
| topic | multiple graph multiple tree divisible graph spanning tree complete spanning tree minimum spanning tree np-completeness |
| url | https://www.mais-journal.ru/jour/article/view/1470 |
| work_keys_str_mv | AT alexandervaleryevichsmirnov npcompletenessoftheminimumspanningtreeproblemofamultiplegraphofmultiplicityk3 |