Kybernetika

Suppose a graph $G=(V,E)$ whose edges are partitioned into $p$ disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories.

We show that polynomiality of this problem depends on the number $p$ of categories and present some polynomial algorithm.