AN 11-6-APPROXIMATION ALGORITHM FOR THE NETWORK STEINER PROBLEM

被引：206

作者：

ZELIKOVSKY, AZ

机构：

[1] Institute of Mathematics, Kishinev, 277028

来源：

ALGORITHMICA | 1993年 / 9卷 / 05期

关键词：

STEINER TREE; APPROXIMATION ALGORITHM;

D O I：

10.1007/BF01187035

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time O(Absolute value of V Absolute value of E + Absolute value of S4), where V is the vertex set, E is the edge set of the graph, and S is the given subset of vertices.

引用

页码：463 / 470

页数：8