Title :
A new efficient approximation algorithm for the Steiner tree problem in rectilinear graphs
Author :
Mastumoto, Tadashi ; Saigan, Naoshi ; Tsuji, Koukichi
Author_Institution :
Dept. of Electr. & Electron. Eng., Fukui Univ., Japan
Abstract :
The Steiner tree problem in a grid graph with all edges having weight 1 is considered. For a given finite set P of the generating points in the grid graph, an approximation algorithm using properties of the Delaunay net and the optimum Steiner tree with three generating points is proposed. It is shown that the complexity of this algorithm does not depend on the number of nodes of a grid graph and is O(k2), where k is the number of the generating points of P. lt is shown that this algorithm always generates the optimum Steiner tree for k⩽4
Keywords :
computational complexity; network topology; trees (mathematics); Delaunay net; Steiner tree problem; approximation algorithm; grid graph; rectilinear graphs; Approximation algorithms; Mesh generation; Polynomials; Steiner trees; Tree graphs; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112610
