FASTER EXACT ALGORITHMS FOR STEINER TREES IN PLANAR NETWORKS

被引：27

作者：

BERN, M

机构：

[1] Xerox Palo Alto Research Center, Palo Alto, California

来源：

NETWORKS | 1990年 / 20卷 / 01期

关键词：

D O I：

10.1002/net.3230200110

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We improve the time and space complexities of dynamic programming algorithms that compute optimal Steiner trees spanning nodes in planar networks. Our algorithms have special application to the rectilinear Steiner problem. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company

引用

页码：109 / 120

页数：12

共 17 条

[1]

BAKER BS, 1983, 24TH P IEEE S F COMP

[2] AVERAGE NUMBER OF MAXIMA IN A SET OF VECTORS AND APPLICATIONS [J].