Generalised k-Steiner Tree Problems in Normed Planes

Details Generalised k-Steiner Tree Problems in Normed Planes Generalised k-Steiner Tree Problems in Normed Planes

2011-11-07

arxiv.org/abs/1111.1464v1

Mathematics

Combinatorics

Scientific paper

The 1-Steiner tree problem, the problem of constructing a Steiner minimum tree containing at most one Steiner point, has been solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane subdivisions called oriented Dirichlet cell partitions. Their algorithm produces an optimal solution within $\mathcal{O}(n^2)$ time. In this paper we generalise their approach in order to solve the $k$-Steiner tree problem, in which the Steiner minimum tree may contain up to $k$ Steiner points for a given constant $k$. We also extend their approach further to encompass arbitrary normed planes, and to solve a much wider class of problems, including the $k$-bottleneck Steiner tree problem and other generalised $k$-Steiner tree problems. We show that, for any fixed $k$, such problems can be solved in $\mathcal{O}(n^{2k})$ time.

Affiliated with

Also associated with

No associations

Rating

Generalised k-Steiner Tree Problems in Normed Planes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalised k-Steiner Tree Problems in Normed Planes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalised k-Steiner Tree Problems in Normed Planes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689192