Steiner Tree Problems and Approximation Methods for Their Solution

journal article - other

English

The aim of this paper was to describe Steiner tree problems, which are an important subset of mimimal network tasks. The only criterion that we used was total length of the network or the total costs for its creating. In spite of their broad application area, Steiner problems are not studied in the Czech literature, which is evidenced by the references. Graph theory books only note these problems as a special case of the mimimum spanning tree problem or even do not mention them at all. We have tried to deal with he problems in this area in a clear way. It refers to tens of other papers often written in a very sketched form, e.g. proofs are very brief, incomplete or not quite general (e.g. the proof of NP-completeness of the RStMTP. Many theorems were formulated and proved by the author without an analogy to literature. The aim was to explain all Steiner tree problems in the same way as the foreign authors often specialize, e.g. Hwang, Warme and Zachariasen in the geometrical problems (rectilinear and Euclidean), Ganley and Robins in the rectilinear one, Voss and Hougardy to the Steiner problem in graphs, Zelikovsky in the rectilinear and graphical problem, etc. Further, in a simple way, it was proved that Eppstein's proof of the Steiner ratio for rectilinear problem is incorrect and its correct modification was proposed [Šeda-Mendel01} based on the original strategy of two spanning trees, however, their different topology does not exceed the bound of 1.50 for the Steiner ratio. Time complexities of many algorithms were recalculated with respect to the use of effecient data structures, e.g. the implementation of priority queues by a binary heap decreased the time complexity of Jarník's and Dijkstra's algorithm and this was projected into two approximation algorithms for Steiner tree problem in graphs. Due to the NP-completeness of the Steiner tree problems, it was not possible to determine an exact solution for large instances. Using a new mathematical model it was shown that even the professional optimization package GAMS (probably based on Branch and Bound Method) can solve only small instances with no more than 50 vertices. On the other hand, a general applicability of metaheuristics for all Steiner tree problems was not confirmed. They surely cannot be recommended for the rectilinear problem, but are promising for the Steiner problem in graphs where the Steiner ratio is high. As for the Euclidean Steiner tree problem its Steiner ratio 2/sqrt(3). shows that the approximation by the Euclidean minimum spanning tree is a very good initial solution and its improvement by simple deterministic heuristic presented here is quite sufficient. In future, we will try to generalize these problems to the fuzzy case where weights of edges will be given by fuzzy numbers. As yet an algorithm has been implemented determining the shortest path with distances described by fuzzy numbers [Šeda-Zittau01], which will be used for a fuzzy variant of the graphical Steiner tree problem.

Minimum spanning tree, Steiner tree, metaheuristic, approximation

ŠEDA, M.

2001

1. 11. 2001

1213-418X

Vědecké spisy Vysokého učení technického v Brně Edice Habilitační a inaugurační spisy

64

XI

Czech Republic

1

26

26