The color-balanced spanning tree problem
Štefan Berežný; Vladimír Lacko
Kybernetika (2005)
- Volume: 41, Issue: 4, page [539]-546
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topBerežný, Štefan, and Lacko, Vladimír. "The color-balanced spanning tree problem." Kybernetika 41.4 (2005): [539]-546. <http://eudml.org/doc/33771>.
@article{Berežný2005,
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 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.},
author = {Berežný, Štefan, Lacko, Vladimír},
journal = {Kybernetika},
keywords = {spanning tree; matroids; algorithms; NP-completeness; spanning tree; matroids; polynomial algorithms; NP-completeness; edge partition},
language = {eng},
number = {4},
pages = {[539]-546},
publisher = {Institute of Information Theory and Automation AS CR},
title = {The color-balanced spanning tree problem},
url = {http://eudml.org/doc/33771},
volume = {41},
year = {2005},
}
TY - JOUR
AU - Berežný, Štefan
AU - Lacko, Vladimír
TI - The color-balanced spanning tree problem
JO - Kybernetika
PY - 2005
PB - Institute of Information Theory and Automation AS CR
VL - 41
IS - 4
SP - [539]
EP - 546
AB - 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.
LA - eng
KW - spanning tree; matroids; algorithms; NP-completeness; spanning tree; matroids; polynomial algorithms; NP-completeness; edge partition
UR - http://eudml.org/doc/33771
ER -
References
top- Averbakh I., Berman O., 10.1016/0167-6377(94)90043-4, Oper. Res. Lett. 16 (1994), 291–297 (1994) Zbl0823.90122MR1316151DOI10.1016/0167-6377(94)90043-4
- 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
- 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 (1999)
- Berežný Š., Lacko V., 10.7151/dmgt.1182, Discuss. Math. Graph Theory 23 (2003), 5–21 Zbl1050.05112MR1987558DOI10.7151/dmgt.1182
- Hamacher H. W., Rendl F., 10.1016/0167-6377(91)90061-S, Oper. Res. Lett. 10 (1991), 211–219 (1991) Zbl0745.90061MR1115858DOI10.1016/0167-6377(91)90061-S
- Lawler E. L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York 1976 Zbl1058.90057MR0439106
- Punnen A. P., 10.1016/0167-6377(92)90069-F, Oper. Res. Lett. 12 (1992), 89–95 (1992) Zbl0768.90077MR1188371DOI10.1016/0167-6377(92)90069-F
- Richey M. B., Punnen A. P., 10.1016/0166-218X(92)90165-7, Discrete Appl. Math. 39 (1992), 147–153 (1992) MR1184685DOI10.1016/0166-218X(92)90165-7
- Rosen K. H., Michaels J. G., Handbook of Discrete and Combinatorial Mathematics, CRC Press, New York 1997 Zbl1044.00002MR1725200
Citations in EuDML Documents
topNotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.