Generalised k-Steiner Tree Problems in the Plane
by Dr Marcus Brazil
Abstract: The 1-Steiner tree problem, the problem of constructing a minimum cost network interconnecting a given set of nodes and containing at most one at most one extra node (known as a Steiner point), was solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane partitions called oriented Dirichlet cells. Their algorithm produces an optimal solution within O(n^2) time. In this seminar we outline their approach, and show how it can be generalised in order to solve the k-Steiner tree problem, in which the minimum network may contain up to k Steiner points, for a given constant k. We also further extend their approach to encompass arbitrary normed planes, and to solve a much broader class of problems, which includes the k-bottleneck Steiner tree problem (where the cost of the network is the length of its maximum length edge, instead of total edge-length) and other generalised k-Steiner tree problems. This work has potential applications to a wide range of areas, including wireless sensor networks. This is joint work with Charl Ras, Konrad Swanepoel and Doreen Thomas.
For More Information: contact: Kerem Akartunali. email: email@example.com