EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2148. An Exact Algorithm for the Euclidean k-Steiner Tree Problem

Invited abstract in session WB-25: Topics in Integer Programming II, stream Combinatorial Optimization.

Wednesday, 10:30-12:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Jae Lee
Mathematics and Statistics, University of Melbourne
2. Charl Ras
School of Mathematics and Statistics, University of Melbourne
3. Marcus Brazil
Dept. Electrical and Electronic Engineering, University of Melbourne
4. Doreen Thomas
Mechanical Engineering, University of Melbourne

Abstract

The classical minimum Steiner tree problem is an NP-hard problem that involves finding the shortest network spanning a set of terminals in the plane using additional points called Steiner points. In the minimum k-Steiner tree problem, the number of Steiner points is limited to some positive integer k. In a minimum Steiner tree, every Steiner point has degree 3, but the restriction on the number of Steiner points also allows degree-4 Steiner points to occur. This increases the number of topologies that are potentially optimal, which further increases the complexity of the problem.

To address the large number of topologies in the classical minimum Steiner tree problem, algorithms such as the GeoSteiner Algorithm implement various pruning tests. These pruning tests are based on the structural and geometric properties of a minimum Steiner tree and are used to discard the majority of sub-optimal topologies early on to deal with the large number of topologies. We take this approach and create novel pruning tests that tackle topologies involving a degree-4 Steiner point. Hence, we create an algorithm that solves the minimum k-Steiner tree problem exactly, incorporating these new pruning tests in order to make it more efficient.

Keywords

Status: accepted

Back to the list of papers