| Title:
|
The color-balanced spanning tree problem (English) |
| Author:
|
Berežný, Štefan |
| Author:
|
Lacko, Vladimír |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
41 |
| Issue:
|
4 |
| Year:
|
2005 |
| Pages:
|
[539]-546 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
spanning tree |
| Keyword:
|
matroids |
| Keyword:
|
algorithms |
| Keyword:
|
NP-completeness |
| MSC:
|
05C05 |
| MSC:
|
05C15 |
| MSC:
|
05C85 |
| MSC:
|
90C27 |
| idZBL:
|
Zbl 1249.05053 |
| idMR:
|
MR2180362 |
| . |
| Date available:
|
2009-09-24T20:11:03Z |
| Last updated:
|
2015-03-23 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135674 |
| . |
| Reference:
|
[1] Averbakh I., Berman O.: Categorized bottleneck/minisum path problems on networks.Oper. Res. Lett. 16 (1994), 291–297 Zbl 0823.90122, MR 1316151, 10.1016/0167-6377(94)90043-4 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[4] Berežný Š., Lacko V.: Balanced problems on graphs with categorization of edges.Discuss. Math. Graph Theory 23 (2003), 5–21 Zbl 1050.05112, MR 1987558, 10.7151/dmgt.1182 |
| Reference:
|
[5] Hamacher H. W., Rendl F.: Color constrained combinatorial optimization problems.Oper. Res. Lett. 10 (1991), 211–219 Zbl 0745.90061, MR 1115858, 10.1016/0167-6377(91)90061-S |
| Reference:
|
[6] Lawler E. L.: Combinatorial Optimization: Networks and Matroids.Holt, Rinehart and Winston, New York 1976 Zbl 1058.90057, MR 0439106 |
| Reference:
|
[7] Punnen A. P.: Traveling salesman problem under categorization.Oper. Res. Lett. 12 (1992), 89–95 Zbl 0768.90077, MR 1188371, 10.1016/0167-6377(92)90069-F |
| Reference:
|
[8] Richey M. B., Punnen A. P.: Minimum weight perfect bipartite matchings and spanning trees under categorizations.Discrete Appl. Math. 39 (1992), 147–153 MR 1184685, 10.1016/0166-218X(92)90165-7 |
| Reference:
|
[9] Rosen K. H., Michaels J. G.: Handbook of Discrete and Combinatorial Mathematics.CRC Press, New York 1997 Zbl 1044.00002, MR 1725200 |
| . |
