Construction of the developing connecting tree. Issue 8 (3rd August 2021)

• Record Type: Journal Article
• Authors: Kirzhner, Valery M.; Ravve, Elena V.; Volkovich, Zeev
• Is Part Of: Engineering optimization. Volume 53:Issue 8(2021)
• Page Start: 1384
• Page End: 1397
• Publication Date: 2021-08-03
• Subjects: Developing connection tree -- Steiner points -- Gilbert–Pollak ratio -- estimation of functional mean value; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2020.1793978
• Languages: English
• ISSNs: 0305-215X

Abstract

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.