Construction of the developing connecting tree. Issue 8 (3rd August 2021) - Kirzhner, Valery M.; Ravve, Elena V.; Volkovich, Zeev
Abstract : A problem of linking vertices (objects) by a connecting tree is studied under the condition that objects appear at different given times. In this case, the target function depends not only on the total length of the connecting tree but also on the times of constructing its fragments. This problem is shown to be NP-complete even when the linking is done without intermediate vertices. In this article, some necessary conditions of optimality of the developing connecting tree are formulated.