Article
Full entry |
PDF
(1.0 MB)
Feedback
PDF
(1.0 MB)
Feedback
Keywords:
spanning tree; matroids; algorithms; NP-completeness
spanning tree; matroids; algorithms; NP-completeness
Summary:
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.
References:
[1] Averbakh I., Berman O.: Categorized bottleneck/minisum path problems on networks. Oper. Res. Lett. 16 (1994), 291–297 DOI 10.1016/0167-6377(94)90043-4 | MR 1316151 | Zbl 0823.90122
[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 10.7151/dmgt.1182 | MR 1987558 | Zbl 1050.05112
[5] Hamacher H. W., Rendl F.: Color constrained combinatorial optimization problems. Oper. Res. Lett. 10 (1991), 211–219 DOI 10.1016/0167-6377(91)90061-S | MR 1115858 | Zbl 0745.90061
[6] Lawler E. L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York 1976 MR 0439106 | Zbl 1058.90057
[7] Punnen A. P.: Traveling salesman problem under categorization. Oper. Res. Lett. 12 (1992), 89–95 DOI 10.1016/0167-6377(92)90069-F | MR 1188371 | Zbl 0768.90077
[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 10.1016/0166-218X(92)90165-7 | MR 1184685
[9] Rosen K. H., Michaels J. G.: Handbook of Discrete and Combinatorial Mathematics. CRC Press, New York 1997 MR 1725200 | Zbl 1044.00002
Search
Partner of
