Balanced problems on graphs with categorization of edges
Štefan Berežný ; Vladimír Lacko
Discussiones Mathematicae Graph Theory, Tome 23 (2003), p. 5-21 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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: L₅(D)=max1≤i≤p(maxe∈Si∩Dw(e)-mine∈Si∩Dw(e)) For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary and for fixed number of categories.

Publié le : 2003-01-01
EUDML-ID : urn:eudml:doc:270439 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1182,
     author = {\v Stefan Bere\v zn\'y and Vladim\'\i r Lacko},
     title = {Balanced problems on graphs with categorization of edges},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {23},
     year = {2003},
     pages = {5-21},
     zbl = {1050.05112},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1182}
}

Štefan Berežný; Vladimír Lacko. Balanced problems on graphs with categorization of edges. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 5-21. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1182/

[000] [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. | Zbl 0823.90122

[001] [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. | Zbl 1003.90525

[002] [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.

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

[004] [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.

[005] [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. | Zbl 0506.90083

[006] [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.

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

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

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

[010] [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. | Zbl 0554.90078

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

[012] [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. | Zbl 0776.05088