Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first last
cannonical link button

http://yadda.icm.edu.pl:80/baztech/element/bwmeta1.element.baztech-article-BPOB-0049-0024

Czasopismo

Przegląd Elektrotechniczny

Tytuł artykułu

Partial Inverse Most Unbalanced Spanning Tree Problem

Autorzy Wang, Q. 
Treść / Zawartość http://pe.org.pl/
Warianty tytułu
PL Częściowo odwrotny najbardziej niezrównoważony problem drzewa rozpinającego
Języki publikacji EN
Abstrakty
EN In this paper, we consider the partial inverse most unbalanced spanning tree problem, which is how to modify the weights of the edges in a simple undirected weighted graph with minimum cost such that the partially given forest is contained in a new most unbalanced spanning tree. Two models are studied: the problem under the weighted Hamming distance and the problem under the weighted l1 norm. We present their respective algorithms that all run in strongly polynomial times.
PL Rozważano częściowo odwrotny najbardziej niezrównoważony problem drzewa rozpinającego, czyli jak modyfikować wagi brzegów niebezpośrednio ważonego grafu. Rozpatrzono dwa modele: ważonego dystansu Hamminga i ważonej normy I1.
Słowa kluczowe
PL grafy   drzewo rozpinające  
EN most unbalanced spanning tree   forest   computational complexity   strongly polynomial time algorithm  
Wydawca Wydawnictwo SIGMA-NOT
Czasopismo Przegląd Elektrotechniczny
Rocznik 2012
Tom R. 88, nr 1b
Strony 111--114
Opis fizyczny Bibliogr. 13 poz.
Twórcy
autor Wang, Q.
  • Department of Mathematics, China Jiliang University, Hangzhou 310018, China, mathqin@126.com
Bibliografia
[1] Ahuja R.K., Orlin J.B., Inverse optimization, part I: Linear programming and general problem, Operations Research Letters, 35 (2001), 771-783.
[2] Orlin J.B., Inverse optimization and partial inverse optimization, PPT Presentation on Optimization Day Columbia University, (2003), November 3.
[3] Heuberger C., Inverse combinatorial optimization: a survey on problems, methods, and results, Journal of Combinatorial Optimization, 8 (2004), 329-361.
[4] Gentry S., Partial inverse linear programming, MIT Lab for Information and Decision Systems Report, LIDS-P-2532 (2001), December.
[5] Yang X.G., Complexity of partial inverse assignment problem and partial inverse cut problem, RAIRO Oper. Res. 35 (2001), 117-126.
[6] Lai T.C., Orlin J.B., The Complexity of Preprocessing, Research Report of Sloan School of Management, MIT, (2003).
[7] Yang X.G., Zhang J.Z., Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems, Computational Optimization and Applications, 36 (2007), 55-66.
[8] Yang X.G., Zhang J.Z., Partial inverse assignment problems under l1 norm, Operations Research Letters, 35 (2007), 23-28.
[9] Cai M.C., Duin C.W., Yang X.G., Zhang J.Z., The partial inverse minimum spanning tree problem when weight increase is forbidden, European Journal of Operational Research, 188 (2008), 348-353.
[10] Camerini P.M., Maffioli F., Martello S., Toth P., Most and least uniform spanning trees, Discrete Applied Mathematics, 15 (1986), 181-197.
[11] Galil Z., Schieber B., On finding most uniform spanning trees, Discrete Applied Mathematics, 20 (1988), 173-175.
[12] Punnen A.P., Nair K.P.K., Constrained balanced optimization problems, Computers and Mathematics with Applications, 37 (1999), 157-163.
[13] Wang Q., Yuan J.J., Zhang J.Z., An inverse model for the most uniform problem, Operations Research Letters, 36 (2008), 26- 30.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BPOB-0049-0024
Identyfikatory