Geodesic
1-Skeletons of the spanning tree problems with additional constraints
Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 4, pp. 453-463

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: spanning tree, 1-skeleton, clique number, NP-complete problem, hamiltonian chain. 
@article{MAIS_2015_22_4_a0,
     author = {V. A. Bondarenko and A. V. Nikolaev and D. A. Shovgenov},
     title = {1-Skeletons of the spanning tree problems with additional constraints},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {453--463},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/}
}
TY  - JOUR
AU  - V. A. Bondarenko
AU  - A. V. Nikolaev
AU  - D. A. Shovgenov
TI  - 1-Skeletons of the spanning tree problems with additional constraints
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2015
SP  - 453
EP  - 463
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/
LA  - ru
ID  - MAIS_2015_22_4_a0
ER  - 
%0 Journal Article
%A V. A. Bondarenko
%A A. V. Nikolaev
%A D. A. Shovgenov
%T 1-Skeletons of the spanning tree problems with additional constraints
%J Modelirovanie i analiz informacionnyh sistem
%D 2015
%P 453-463
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/
%G ru
%F MAIS_2015_22_4_a0
V. A. Bondarenko; A. V. Nikolaev; D. A. Shovgenov. 1-Skeletons of the spanning tree problems with additional constraints. Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 4, pp. 453-463. http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/