Construction of the developing connecting tree

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.

Keywords:

• Developing connection tree
• Steiner points
• Gilbert–Pollak ratio
• estimation of functional mean value

Acknowledgments

The authors would like to thank the referees for their careful reading and constructive suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.