Geodesic
Balanced problems on graphs with categorization of edges
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 1, pp. 5-21.

Voir la notice de l'article provenant de la source Library of Science

Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function:
Keywords: algorithms on graphs, categorization of edges, NP-completeness 
@article{DMGT_2003_23_1_a0,
     author = {Bere\v{z}n\'y, \v{S}tefan and Lacko, Vladim{\'\i}r},
     title = {Balanced problems on graphs with categorization of edges},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--21},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_1_a0/}
}
TY  - JOUR
AU  - Berežný, Štefan
AU  - Lacko, Vladimír
TI  - Balanced problems on graphs with categorization of edges
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 5
EP  - 21
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_1_a0/
LA  - en
ID  - DMGT_2003_23_1_a0
ER  - 
%0 Journal Article
%A Berežný, Štefan
%A Lacko, Vladimír
%T Balanced problems on graphs with categorization of edges
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 5-21
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_1_a0/
%G en
%F DMGT_2003_23_1_a0
Berežný, Štefan; Lacko, Vladimír. Balanced problems on graphs with categorization of edges. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 1, pp. 5-21. http://geodesic.mathdoc.fr/item/DMGT_2003_23_1_a0/

[1] I. Averbakh and O. Berman, Categorized bottleneck-minisum path problems on networks, Oper. Res. Letters 16 (1994) 291-297, doi: 10.1016/0167-6377(94)90043-4.

[2] S. Berezný, K. Cechlárová and V. Lacko, Optimization problems on graphs with categorization of edges, in: Proc. SOR 2001, eds. V. Rupnik, L. Zadnik-stirn, S. Drobne (Preddvor, Slovenia, 2001) 171-176.

[3] S. Berezný, K. Cechlárová and V. Lacko, A polynomially solvable case of optimization problems on graphs with categorization of edges, in: Proc. of MME'1999 (Jindrichúv Hradec, 1999) 25-31.

[4] S. Berezný and V. Lacko, Special problems on graphs with categorization, in: Proc. of MME'2000 (Praha, 2000) 7-13.

[5] S. Berezný and V. Lacko, Easy (polynomial) problems on graphs with categorization, in: Proc. of New trends of aviation development (Air Force Academy of gen. M.R. Stefánik, Košice, 2000) 36-46.

[6] G. Cornuéjols, D. Naddef and W.R. Pulleyblank, Halin graphs and the Travelling salesman problem, Mathematical Programming 26 (1983) 287-294, doi: 10.1007/BF02591867.

[7] C.W. Duin and A. Volgenant, Minimum deviation and balanced optimization: A unified aproach, Operation Research Letters 10 (1991) 43-48, doi: 10.1016/0167-6377(91)90085-4.

[8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, New York, 1979).

[9] M. Gavalec and O. Hudec, Balanced Location on a Graph, Optimization, 35 (1995) 367-372, doi: 10.1080/02331939508844156.

[10] V. Lacko, Persistency in Traveling Salesman Problem on Halin graphs, Discuss. Math. Graph Theory 20 (2000) 231-242, doi: 10.7151/dmgt.1122.

[11] S. Martello, W.R. Pulleyblank, P. Toth and D. de Werra, Balanced optimization problems, Oper. Res. Lett. 3 (1984) 275-278, doi: 10.1016/0167-6377(84)90061-0.

[12] A.P. Punnen, Traveling salesman problem under categorization, Oper. Res. Lett. 12 (1992) 89-95, doi: 10.1016/0167-6377(92)90069-F.

[13] M.B. Richey and A.P. Punnen, Minimum weight perfect bipartite matchings and spanning trees under categorizations, Discrete Appl. Math. 39 (1992) 147-153.