Partial Inverse Most Unbalanced Spanning Tree Problem

• Autorzy: Wang Q.

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

EN

most unbalanced spanning tree; forest; computational complexity; strongly polynomial time algorithm

PL

grafy; drzewo rozpinające

• 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,

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.