Speaker
Mr
Dmitriy Lotarev
(A.A. Kharkevich Institute for Information Transmission Problems, RAS)
Description
The problem of allocation of Steiner points in Euclidean Steiner Tree is considered. In spite of advances in wireless technologies, many computer networks utilize cables as a physical medium for devices to transfer data. Such networks are allocated on the earth's surface and problem is to minimize the cost of network to connect the computers. The cost of network is sum of building costs and cost of the information transportation. Euclidean Steiner tree problem in the form of topological network design is a good model of this problem.
The package MatLab allows looking for the solution of this model problem... It consists of two parts — to define the adjacency matrix and allocate the Steiner points. The package MatLab has the way to solve the second part of this problem — allocate Steiner points under condition that the adjacency matrix is set. The method to get solution has been worked out. The Steiner tree is formed by means of solving of the sequence of "three points" Steiner problems [1]. MatLab solves "Three points" Steiner problem by means of function Xmin = fminsearch (hFunction, x0). Function "Function" define current sum of distances from current point to three given points. MatLab searches minimum of the sum by means of Nelder-Mead simplex method [2]. Minimum point is Steiner point of "three points" Steiner tree. It is first remarkable vertex of "three points" Steiner tree problem.
Adjacent to root a new vertex, named "equivalent vertex", is defined. It is second remarkable vertex of "three points" problem. It is remarrable because of the cost of edge connecting this vertex and root is the same as the cost of the entire "Three points" Steiner tree.
Steiner tree problem for several terminal points is solved in two stages. First of all "equivalent vertexes" are allocated. It is first sage. The "equivalent vertexes" are used to allocate Steiner points. It is second stage. The package MatLab allows looking graphic view of the results.
1. Лотарев Д. Т. Решение трехточечной задачи Штейнера на плоскости средствами MatLab. Труды ИСА РАН, 2008. Т. 32. стр. 159-165.
2. Д.Г. Мэтьюз, К.Д. Финк. Численные методы. Использование MatLab. Издательский дом "Вильямс" Москва, Санкт-Петерсбург, Киев. 2001.
Primary author
Mr
Dmitriy Lotarev
(A.A. Kharkevich Institute for Information Transmission Problems, RAS)
