Geodesic
The color-balanced spanning tree problem
Kybernetika, Tome 41 (2005) no. 4, pp. 539-546 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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--546},
     year = {2005},
     volume = {41},
     number = {4},
     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
EP  - 546
VL  - 41
IS  - 4
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-546
%V 41
%N 4
%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, pp. 539-546. http://geodesic.mathdoc.fr/item/KYB_2005_41_4_a7/

[1] Averbakh I., Berman O.: Categorized bottleneck/minisum path problems on networks. Oper. Res. Lett. 16 (1994), 291–297 | DOI | MR | Zbl

[2] Berežný Š., Cechlárová, K., Lacko V.: Optimization problems on graphs with categorization of edges. In: Proc. SOR 2001 (V. Rupnik, L. Zadnik-Stirn, and S. Drobne, eds.), Slovenian Society Informatika – Section for Operational Research, Predvor Slovenia 2001, pp. 171–176

[3] Berežný Š., Cechlárová, K., Lacko V.: A polynomially solvable case of optimization problems on graphs with categorization of edges. In: Proc. 17th Internat. Conference Mathematical Methods in Economics ’99 (J. Plešingr, ed.), Czech Society for Operations Research, Jindřichův Hradec 1999, pp. 25–31

[4] Berežný Š., Lacko V.: Balanced problems on graphs with categorization of edges. Discuss. Math. Graph Theory 23 (2003), 5–21 | DOI | MR | Zbl

[5] Hamacher H. W., Rendl F.: Color constrained combinatorial optimization problems. Oper. Res. Lett. 10 (1991), 211–219 | DOI | MR | Zbl

[6] Lawler E. L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York 1976 | MR | Zbl

[7] Punnen A. P.: Traveling salesman problem under categorization. Oper. Res. Lett. 12 (1992), 89–95 | DOI | MR | Zbl

[8] Richey M. B., Punnen A. P.: Minimum weight perfect bipartite matchings and spanning trees under categorizations. Discrete Appl. Math. 39 (1992), 147–153 | DOI | MR

[9] Rosen K. H., Michaels J. G.: Handbook of Discrete and Combinatorial Mathematics. CRC Press, New York 1997 | MR | Zbl