Abstract
The definition of a shortest spanning tree of a graph is generalized to that of an efficient spanning tree for graphs with vector weights, where the notion of optimality is of the Pareto type. An algorighm for obtaining all efficient spanning trees is presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Corley, H. W., andMoon, I. D.,Shortest Paths in Networks with Vector Weights, Journal of Optimization Theory and Applications (to appear).
Christofides, N.,Graph Theory: An Algorithmic Approach, Academic Press, New York, New York, 1975.
Prim, R. C.,Shortest Connection Networks and Some Generalizations, Bell System Technical Journal, Vol. 36, pp. 1389–1401, 1957.
Geoffrion, A. M.,Proper Efficiency and the Theory of Vector Maximization, Journal of Mathematical Analysis and Applications, Vol. 22, pp. 618–630, 1968.
Standish, T. A.,Data Structure Techniques, Addison-Wesley, Reading, Massachusetts, 1980.
Zahn, C. T.,Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters, IEEE Transactions on Computers, Vol. C-20, pp. 68–86, 1971.
Held, M., andKarp, R. M.,The Traveling Salesman Problem and Minimum Spanning Trees, Operations Research, Vol. 18, pp. 1138–1162, 1970.
Gomory, R. E., andHu, R. C.,Multi-Terminal Network Flows, SIAM Journal on Applied Mathematics, Vol. 9, pp. 551–571, 1961.
Author information
Authors and Affiliations
Additional information
Communicated by C. T. Leondes
Rights and permissions
About this article
Cite this article
Corley, H.W. Efficient spanning trees. J Optim Theory Appl 45, 481–485 (1985). https://doi.org/10.1007/BF00938448
Issue Date:
DOI: https://doi.org/10.1007/BF00938448