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

Abstract

top
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 ) = m a x 1 ≤ i ≤ p ( m a x e ∈ S i ∩ D w ( e ) - m i n 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.

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. [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. [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. [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. [4] S. Berezný and V. Lacko, Special problems on graphs with categorization, in: Proc. of MME'2000 (Praha, 2000) 7-13. Zbl1050.05112
  5. [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. [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. [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. [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. [9] M. Gavalec and O. Hudec, Balanced Location on a Graph, Optimization, 35 (1995) 367-372, doi: 10.1080/02331939508844156. Zbl0874.90114
  10. [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. [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. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.