Geodesic
Polytops of binary trees, structure of the polytop for the >--tree
Čebyševskij sbornik, Tome 23 (2022) no. 4, pp. 136-151

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

In the paper minimal fillings of finite metric spaces are investigated. This object appeared as a generalization of the concepts of a shortest tree and a minimal filling in the sense of Gromov. It is known that the weight of a minimal filling of a given type can be found by linear programming and by so-called multitours technique. A relation between theses two approaches can be demonstrated using duality in linear programming, namely, rational points of the polytop constructed by the dual problem correspond to multitours. The paper is devoted to investigation of such polytopes, It is shown that the vertices of the polytop are in one-to-one correspondence with irreducible multitours. A description of the polytop and an explicit formula for the weight of the minimal filling of the «snake–type» binary tree is obtained.
Keywords: finite metric space, minimal filling, linear programming, duality, convex polytops. 
@article{CHEB_2022_23_4_a11,
     author = {O. S. Shcherbakov},
     title = {Polytops of binary trees, structure of the polytop for the <<snake--type>>--tree},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {136--151},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/}
}
TY  - JOUR
AU  - O. S. Shcherbakov
TI  - Polytops of binary trees, structure of the polytop for the <>--tree
JO  - Čebyševskij sbornik
PY  - 2022
SP  - 136
EP  - 151
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/
LA  - ru
ID  - CHEB_2022_23_4_a11
ER  - 
%0 Journal Article
%A O. S. Shcherbakov
%T Polytops of binary trees, structure of the polytop for the <>--tree
%J Čebyševskij sbornik
%D 2022
%P 136-151
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/
%G ru
%F CHEB_2022_23_4_a11
O. S. Shcherbakov. Polytops of binary trees, structure of the polytop for the <>--tree. Čebyševskij sbornik, Tome 23 (2022) no. 4, pp. 136-151. http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/