| |
|
|
Abstract: 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 wanted 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. Contact the authors: lacko@science.upjs.sk, Stefan.Berezny@tuke.sk Download PDF version of the preprint. |