Abstract
We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).
Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).
P.M. Camerini, G. Galbiati and F. Maffioli, The complexity of weighted multi-constrained spanning tree problems,Colloquium on the Theory of Algorithms, Pecs (1984).
S. Chung, H.W. Hamacher, F. Maffioli and K.G. Murty, A note on combinatorial optimization with max-linear objective functions, Discr. Appl. Math. 42 (1993) 139–145.
H.W. Corley, Efficient spanning trees, J. Optim. Theory Appl. 45 (1985) 481–485.
Z. Drezner and S.Y. Nof, On optimizing bin packing and insertion plans for assembly robots, IEE Trans. 16 (1984) 262–270.
H.N. Gabow, Two algorithms for generating weighted spanning trees in order, SIAM J. Comp. 6 (1977) 139–150.
A.M. Geoffrion, Proper efficiency and the theory of vector optimization, J. Math. Anal. Appl. 22 (1968) 618–630.
F. Glover, D. Klingman, R. Krishnan and R. Padman, An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem, Eur. J. Oper. Res. 56 (1992) 343–356.
R.E. Gomory and T.C. Hu, Multiterminal network flows, SIAM J. Appl. Math. 9 (1961) 551–571.
H.W. Hamacher and C. Hüsselmann, Ranking approach to max-ordering combinatorial optimization and network flows, Report Nr. 246, Fachbereich Mathematik, Universität Kaiserslautern (1993).
H.W. Hamacher and M. Queyranne,K best solutions to combinatorial optimization problems, Ann. Oper. Res. 4 (1985) 123–143.
M. Held and R.M. Karp, The traveling salesman problem and minimum spanning trees, Oper. Res. 18 (1970) 1138–1162.
N. Katoh, T. Ibaraki and H. Mine, An algorithm for findingk minimum spanning trees, SIAM J. Comp. 10 (1981) 247–255.
J.B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. AMS 7 (1956) 48–50.
U. Lebrecht, Max-Lineare Zuordnungsprobleme in der Roboteroptimierung, Diplomarbeit, Universität Kaiserslautern, Fachbereich Mathematik (1991).
S. Nickel, private communication (1992).
R.C. Prim, Shortest connection networks and some generalizations, Bell Syst. Techn. J. 36 (1957) 1389–1401.
G. Righini and A. Colorni, Max-linear combinatorial optimization, Politecnico di Milano, Dipartimento d. Elettronica, report n. 91.005 (1991).
Author information
Authors and Affiliations
Additional information
Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.
Partially supported by Alexander von Humboldt-Stiftung.
Rights and permissions
About this article
Cite this article
Hamacher, H.W., Ruhe, G. On spanning tree problems with multiple objectives. Ann Oper Res 52, 209–230 (1994). https://doi.org/10.1007/BF02032304
Issue Date:
DOI: https://doi.org/10.1007/BF02032304