Multicriteria Steiner tree with the cost of Steiner vertices

作者: M. Sh. Levin , A. A. Zamkovoy

DOI: 10.1134/S1064226911120059

关键词:

摘要: The multicriteria problem of constructing the Steiner tree with consideration for cost additional vertices is studied. Formulations problems covering trees and algorithmic approaches are described. engineering formulation aimed at a telecommunications network allowance spatial distribution radio interferences. An approach to solving formulated milticriterion on basis combination two schemes proposed: (1) basic scheme clustering initial graph (2) general number calculation Pareto-efficient solutions. A module based modified Prim’s algorithm additionally used. clustered hierarchical algorithm. Examples computational experiment given.

参考文章(42)
Mark Sh. Levin, Towards hierarchical clustering CSR'07 Proceedings of the Second international conference on Computer Science: theory and applications. pp. 205- 215 ,(2007)
Pawel Winter, Dana Scott Richards, Frank Hwang, The Steiner Tree Problem ,(1992)
Mark Sh. Levin, STUDENT RESEARCH PROJECTS IN SYSTEM DESIGN international conference on computer supported education. pp. 67- 72 ,(2009)
Stefan Voß, Steiner Tree Problems in Telecommunications Handbook of Optimization in Telecommunications. pp. 459- 492 ,(2006) , 10.1007/978-0-387-30165-5_18
D. M. Warme, P. Winter, M. Zachariasen, Exact Algorithms for Plane Steiner Tree Problems: A Computational Study Kluwer Academic Publishers. pp. 81- 116 ,(2000) , 10.1007/978-1-4757-3171-2_6
Derek R. Dreyer, Michael L. Overton, Two Heuristics for the Euclidean Steiner Tree Problem Journal of Global Optimization. ,vol. 13, pp. 95- 106 ,(1998) , 10.1023/A:1008285504599
Peter C. Fishburn, Utility theory for decision making ,(1970)
Mark Sh. Levin, Towards Hierarchical Clustering (Extended Abstract) Computer Science – Theory and Applications. pp. 205- 215 ,(2007) , 10.1007/978-3-540-74510-5_22
Xiuzhen Cheng, Yingshu Li, Ding-Zhu Du, Hung Q. Ngo, Steiner Trees in Industry Springer, Boston, MA. pp. 193- 216 ,(2002) , 10.1007/0-387-23830-1_4