Premium
Faster exact algorithms for steiner trees in planar networks
Author(s) -
Bern Marshall
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200110
Subject(s) - steiner tree problem , planar , algorithm , spanning tree , computer science , dynamic programming , planar graph , mathematics , combinatorics , graph , computer graphics (images)
Abstract 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.