School Seminars and Colloquia

Generalised k-Steiner Tree Problems in the Plane

ORSUM Seminar

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