KIAM Main page Web Library  •  Publication Searh  Русский 

Conference material: "Academician O.B. Lupanov XIV International Scientific Seminar "Discrete Mathematics and Its Applications" (20-25 June 2022, Moscow)"
Authors: Shcherbakov O.S.
Binary trees polyhedra
n this paper, we study minimal fillings of finite metric spaces (an object that arose as a generalization of the concepts of the shortest tree and minimal filling in the sense of Gromov). As you know, the weight minimum filling of a given type can be found as a solution linear programming problems or using the so-called multitours. The relationship between these two approaches can be seen passing to the dual problem of linear programming: rational points of a convex polyhedron, which is constructed according to the type of filling, correspond to multitours. This work is devoted to the study of such polyhedra. It is shown that their vertices correspond to irreducible multitours. A description of the polyhedron and an explicit weight formula are obtained for the minimum parametric filling of a binary tree of type 'snake'.
polyyhedra, binary trees
Publication language: russian,  pages: 3 (p. 245-247)
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Shcherbakov Oleg Sergeevich,  Lomonosov Moscow State University