1-Skeletons of the Spanning Tree Problems with Additional Constraints
In this paper, we study polyhedral properties of two spanning tree problems with additional constraints. In the first problem, it is required to find a tree with a minimum sum of edge weights among all spanning trees with the number of leaves less than or equal to a given value. In the second proble...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2015-08-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/265 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849240777614426112 |
|---|---|
| author | V. A. Bondarenko A. V. Nikolaev D. A. Shovgenov |
| author_facet | V. A. Bondarenko A. V. Nikolaev D. A. Shovgenov |
| author_sort | V. A. Bondarenko |
| collection | DOAJ |
| description | In this paper, we study polyhedral properties of two spanning tree problems with additional constraints. In the first problem, it is required to find a tree with a minimum sum of edge weights among all spanning trees with the number of leaves less than or equal to a given value. In the second problem, an additional constraint is the assumption that the degree of all nodes of the spanning tree does not exceed a given value. The recognition versions of both problems are NP-complete. We consider polytopes of these problems and their 1-skeletons. We prove that in both cases it is a NP-complete problem to determine whether the vertices of 1-skeleton are adjacent. Although it is possible to obtain a superpolynomial lower bounds on the clique numbers of these graphs. These values characterize the time complexity in a broad class of algorithms based on linear comparisons. The results indicate a fundamental difference between combinatorial and geometric properties of the considered problems from the classical minimum spanning tree problem. |
| format | Article |
| id | doaj-art-0b7e97d34a4b4a2aa0001ad7114bd086 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2015-08-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-0b7e97d34a4b4a2aa0001ad7114bd0862025-08-20T04:00:26ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172015-08-0122445346310.18255/1818-1015-2015-4-453-4632511-Skeletons of the Spanning Tree Problems with Additional ConstraintsV. A. Bondarenko0A. V. Nikolaev1D. A. Shovgenov2P.G. Demidov Yaroslavl State UniversityP.G. Demidov Yaroslavl State UniversityP.G. Demidov Yaroslavl State UniversityIn this paper, we study polyhedral properties of two spanning tree problems with additional constraints. In the first problem, it is required to find a tree with a minimum sum of edge weights among all spanning trees with the number of leaves less than or equal to a given value. In the second problem, an additional constraint is the assumption that the degree of all nodes of the spanning tree does not exceed a given value. The recognition versions of both problems are NP-complete. We consider polytopes of these problems and their 1-skeletons. We prove that in both cases it is a NP-complete problem to determine whether the vertices of 1-skeleton are adjacent. Although it is possible to obtain a superpolynomial lower bounds on the clique numbers of these graphs. These values characterize the time complexity in a broad class of algorithms based on linear comparisons. The results indicate a fundamental difference between combinatorial and geometric properties of the considered problems from the classical minimum spanning tree problem.https://www.mais-journal.ru/jour/article/view/265spanning tree1-skeletonclique numbernp-complete problemhamiltonian chain |
| spellingShingle | V. A. Bondarenko A. V. Nikolaev D. A. Shovgenov 1-Skeletons of the Spanning Tree Problems with Additional Constraints Моделирование и анализ информационных систем spanning tree 1-skeleton clique number np-complete problem hamiltonian chain |
| title | 1-Skeletons of the Spanning Tree Problems with Additional Constraints |
| title_full | 1-Skeletons of the Spanning Tree Problems with Additional Constraints |
| title_fullStr | 1-Skeletons of the Spanning Tree Problems with Additional Constraints |
| title_full_unstemmed | 1-Skeletons of the Spanning Tree Problems with Additional Constraints |
| title_short | 1-Skeletons of the Spanning Tree Problems with Additional Constraints |
| title_sort | 1 skeletons of the spanning tree problems with additional constraints |
| topic | spanning tree 1-skeleton clique number np-complete problem hamiltonian chain |
| url | https://www.mais-journal.ru/jour/article/view/265 |
| work_keys_str_mv | AT vabondarenko 1skeletonsofthespanningtreeproblemswithadditionalconstraints AT avnikolaev 1skeletonsofthespanningtreeproblemswithadditionalconstraints AT dashovgenov 1skeletonsofthespanningtreeproblemswithadditionalconstraints |