Geodesic
The color-balanced spanning tree problem
Kybernetika, Tome 41 (2005) no. 4, p. [539]

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 05C05, 05C15, 05C85, 90C27
Keywords: spanning tree; matroids; algorithms; NP-completeness 
@article{KYB_2005__41_4_a7,
     author = {Bere\v{z}n\'y, \v{S}tefan and Lacko, Vladim{\'\i}r},
     title = {The color-balanced spanning tree problem},
     journal = {Kybernetika},
     pages = {[539]},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2005},
     mrnumber = {2180362},
     zbl = {1249.05053},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2005__41_4_a7/}
}
TY  - JOUR
AU  - Berežný, Štefan
AU  - Lacko, Vladimír
TI  - The color-balanced spanning tree problem
JO  - Kybernetika
PY  - 2005
SP  - [539]
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2005__41_4_a7/
LA  - en
ID  - KYB_2005__41_4_a7
ER  - 
%0 Journal Article
%A Berežný, Štefan
%A Lacko, Vladimír
%T The color-balanced spanning tree problem
%J Kybernetika
%D 2005
%P [539]
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2005__41_4_a7/
%G en
%F KYB_2005__41_4_a7
Berežný, Štefan; Lacko, Vladimír. The color-balanced spanning tree problem. Kybernetika, Tome 41 (2005) no. 4, p. [539]. http://geodesic.mathdoc.fr/item/KYB_2005__41_4_a7/