PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | 23 | 1 | 5-21
Tytuł artykułu

Balanced problems on graphs with categorization of edges

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
23
Numer
1
Strony
5-21
Opis fizyczny
Daty
wydano
2003
otrzymano
2000-12-18
poprawiono
2002-05-06
Twórcy
  • Air Force Academy of M.R. Štefánik, Košice, Rampová 7, 041 21 Košice, Slovakia
  • Institute of Mathematics, University of P.J. Šafárik, Košice, Jesenná 5, 041 54 Košice, Slovakia
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1182
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.