School Seminars and Colloquia

Preprocessing obstacles for Steiner tree problems in Minkowski planes

Discrete Structures and Algorithms (Seminar)

by Marcus Gordon Volz

Institution: The University of Melbourne
Date: Thu 21st September 2017
Time: 11:00 AM
Location: Room 107, Peter Hall Building

Abstract: The obstacle-avoiding Steiner tree problem asks for a shortest embedded network spanning a given set of points such that no part of the network intersects the interiors of a given set of obstacles. The efficiency of exact algorithms for constructing minimum obstacle-avoiding Steiner trees can be improved by reducing the number of vertices and edges that need to be considered for the given obstacles. In this talk we introduce new methods for simplifying the geometry of obstacles for Steiner tree problems in Minkowski planes, and demonstrate their effectiveness by performing experimental results on randomly-generated obstacles in different metrics.

For More Information: Contact: Sanming Zhou. email: