The problem of filling growing treeswith a source located at the root

Abstract

The paper considers the optimization problem of filling growing trees with a source located at the root. Algorithms of work of this source are constructed for filling the graph that minimizes the time of filling the tree root. The case is completely considered when the number of arcs emanating from the root does not exceed 3, and the source power does not exceed 2. Then some more general cases are studied when the source power and the number of root subtrees are arbitrary. Theorems on the existence of optimal parallel tree filling strategies for some general cases are formulated and proved, and the optimal strategies themselves are described. It is proposed to improve the constructed tree filling algorithm by reducing the number of source power switching between root subtrees. Illustrative examples are provided for all results.