Polynomially solvable special cases of the Steiner problem in planar networks (Q1179749): Difference between revisions

Given is an \(n\)-vertex graph \(G\) with edge lengths and a subset of its vertices. The Steiner problem on networks asks for a minimum length tree in \(G\) that includes the input vertices called terminals. The authors give algorithms for two special cases of the Steiner problem: (1) the underlying network is planar and all terminals lie within a bounded number of ``layers'' of a single face, and (2) the problem is the rectilinear Steiner problem and the number of rectilinear convex hulls in the entire ``onion'' of convex hulls is bounded. Both algorithms are based on the dynamic programming approach and run in polynomial time. Nevertheless, they have rather a theoretical significance, since the first algorithm can be implemented to run in \(O(n^ 4)\) time while the second has the complexity of \(O(n^{11})\) for terminals with onion depth 2.