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.
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.