# Balanced problems on graphs with categorization of edges

Štefan Berežný; Vladimír Lacko

Discussiones Mathematicae Graph Theory (2003)

- Volume: 23, Issue: 1, page 5-21
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topŠtefan Berežný, and Vladimír Lacko. "Balanced problems on graphs with categorization of edges." Discussiones Mathematicae Graph Theory 23.1 (2003): 5-21. <http://eudml.org/doc/270439>.

@article{ŠtefanBerežný2003,

abstract = {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) = max_\{1≤i≤p\} (max_\{e ∈ S_i ∩ D\} w(e) - min_\{e ∈ S_i ∩ D\} w(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.},

author = {Štefan Berežný, Vladimír Lacko},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {algorithms on graphs; categorization of edges; NP-completeness; optimization problems},

language = {eng},

number = {1},

pages = {5-21},

title = {Balanced problems on graphs with categorization of edges},

url = {http://eudml.org/doc/270439},

volume = {23},

year = {2003},

}

TY - JOUR

AU - Štefan Berežný

AU - Vladimír Lacko

TI - Balanced problems on graphs with categorization of edges

JO - Discussiones Mathematicae Graph Theory

PY - 2003

VL - 23

IS - 1

SP - 5

EP - 21

AB - 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) = max_{1≤i≤p} (max_{e ∈ S_i ∩ D} w(e) - min_{e ∈ S_i ∩ D} w(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.

LA - eng

KW - algorithms on graphs; categorization of edges; NP-completeness; optimization problems

UR - http://eudml.org/doc/270439

ER -

## References

top- [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. Zbl0823.90122
- [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. Zbl1003.90525
- [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. Zbl1050.05112
- [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. Zbl0506.90083
- [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). Zbl0411.68039
- [9] M. Gavalec and O. Hudec, Balanced Location on a Graph, Optimization, 35 (1995) 367-372, doi: 10.1080/02331939508844156. Zbl0874.90114
- [10] V. Lacko, Persistency in Traveling Salesman Problem on Halin graphs, Discuss. Math. Graph Theory 20 (2000) 231-242, doi: 10.7151/dmgt.1122. Zbl0982.05064
- [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. Zbl0554.90078
- [12] A.P. Punnen, Traveling salesman problem under categorization, Oper. Res. Lett. 12 (1992) 89-95, doi: 10.1016/0167-6377(92)90069-F. Zbl0768.90077
- [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. Zbl0776.05088

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.