Convexity and the Steiner tree problem
作者:
J. Scott Provan,
期刊:
Networks
(WILEY Available online 1988)
卷期:
Volume 18,
issue 1
页码: 55-72
ISSN:0028-3045
年代: 1988
DOI:10.1002/net.3230180108
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractWe investigate the role convexity plays in the efficient solution to the Steiner tree problem. In general terms, we show that a Steiner tree problem is always computationally easier to solve when the points to be connected lie on the boundary of a “convex” region. For the Steiner tree problem on graphs and the rectilinear Steiner tree problem, we give definitions of “convexity” for which this condition is sufficient to allow a polynomial algorithm for finding the optimal Steiner tree. For the classical Steiner tree problem, we show that for the standard definition of convexity, this condition is sufficient to allow a fully polynomial approximation
点击下载:
PDF
(968KB)
返 回