DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 23(1) (2003) 5-21
DOI: https://doi.org/10.7151/dmgt.1182

BALANCED PROBLEMS ON GRAPHS WITH CATEGORIZATION OF EDGES

Stefan Berezný

Air Force Academy of M.R. Stefánik, Košice
Rampová 7, 041 21 Košice, Slovakia

 Vladimír Lacko

Institute of Mathematics
University of P.J. Safárik, Košice
Jesenná 5, 041 54 Košice, Slovakia
e-mail: lacko@science.upjs.sk

Abstract

Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S1,... ,Sp is given. We consider optimization problems P on G defined by a family of feasible sets D(G) and the following objective function:
L5(D)
=

max
1 ≤ i ≤ p 
 ⎛
⎝
max
e ∈ Si∩D 
 w(e)−
min
e ∈ Si∩D 
 w(e) ⎞
⎠

For an arbitrary number of categories we show that the L5-perfect matching, L5-a-b path, L5-spanning tree problems and L5-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. 

Keywords: algorithms on graphs, categorization of edges, NP-completeness.

2000 Mathematics Subject Classification: 05C85, 90C27, 68Q17.

References

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

Received 18 December 2000
Revised 6 May 2002

Close