The Steiner tree problem for terminals on the boundary of a rectilinear polygon (Q1566725)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The Steiner tree problem for terminals on the boundary of a rectilinear polygon |
scientific article; zbMATH DE number 1454563
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The Steiner tree problem for terminals on the boundary of a rectilinear polygon |
scientific article; zbMATH DE number 1454563 |
Statements
The Steiner tree problem for terminals on the boundary of a rectilinear polygon (English)
0 references
4 June 2000
0 references
Given a simple rectilinear polygon P with \(k\) sides and \(n\) terminals on its boundary, we present an \(O(k^{3}n)\)-time algorithm to compute the minimal rectilinear Steiner tree lying inside P interconnecting the terminals. We obtain our result by proving structural properties of a selective set of minimal Steiner trees and exploiting them in a dynamic programming algorithm.
0 references
Rectilinear Steiner tree
0 references
Homotpic routing
0 references
Dynamic programming
0 references
0 references
0 references
0.92099977
0 references
0.9169733
0 references
0.9166432
0 references
0.9117312
0 references
0 references
0.9103627
0 references
