# Generalised k-Steiner Tree Problems in the Plane

*by Dr Marcus Brazil*

*Institution:*Department of Electrical and Electronic Engineering, The University of Melbourne

*Date: Fri 26th June 2009*

*Time: 2:00 PM*

*Location: Russell Love Theatre, Richard Berry Building*

*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: kerema@unimelb.edu.au