Title: Exact Solutions for k-Steiner Tree Problems

Speaker: Jae Lee
The University of Melbourne

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.

—

This event is Hybrid: Seminar to start 16:00 on Zoom and in-person

Location for in person: * Please arrive early to get a cup of tea and get settled in for a 4pm sharp start*
Melbourne Connect, Level 8, Room 8109, 700 Swanston Street, Carlton 

SEMINAR: WED 19 MARCH 2025 16:00 -17:00 (AEDT, Melbourne Time)
ZOOM MEETING ID: 873 1557 5255; PASSWORD: 778635