Speaker: Jae Lee | University of Melbourne
Title: Exact Solutions for k-Steiner Tree Problems
Summary:
We rely on networks for communication, transportation and many other aspects of our daily lives. It is crucial to design these networks with efficiency and optimality in mind. Introducing additional nodes, called Steiner points, allows the design of more efficient networks. However, these Steiner points correspond to junctions of networks, which can be costly and may need to satisfy additional constraints. This motivates the k-Steiner tree problem where the number of Steiner points is restricted to some nonnegative integer k. This constraint on the number of Steiner points increases the complexity of the problem due to a difference in the topology and geometry of the resulting network. In this seminar, we present two exact algorithms that solve the k-Steiner tree problem for two different cost functions. Furthermore, we introduce various pruning tests to make the algorithms run more efficiently.
Biography:
Jae is undertaking a PhD at the University of Melbourne, focusing on creating exact algorithms for Steiner tree problems. He is supervised by Associate Professor Charl Ras, Associate Professor Marcus Brazil and Professor Emeritus Doreen Anne Thomas.
