Optimal enclosing regions in planar graphs
作者:
Daniel Bienstock,
Clyde L. Monma,
期刊:
Networks
(WILEY Available online 1989)
卷期:
Volume 19,
issue 1
页码: 79-94
ISSN:0028-3045
年代: 1989
DOI:10.1002/net.3230190107
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractIn this paper we study the problem of finding a minimum‐weight collection of edges in a planar graph which separates a given set of vertices from the outer face. This problem has two variants: either a given embedding is specified, or the best possible embedding is to be found. We present polynomial‐time algorithms for each case. We show how to use these results to recognize a special case of the steiner tree problem in graphs which is polynomially solvable. A closely related problem is shown to beNP‐com
点击下载:
PDF
(942KB)
返 回