Fast heuristics for solving Steiner tree problems in a graph while minimizing the longest path



Xu, Ming

Journal Title

Journal ISSN

Volume Title


University of Guelph


The 'Steiner tree Problem in a Graph' ('SPG'), which aims to find a minimum-cost tree spanning all terminal vertices in a graph, is an NP-complete problem with numerous practical applications. A useful and interesting extensions to the SPG, referred to as the 'Minimum Longest-Path' ('MLP') SPCA is to also require that the length of the longest path in the tree to be as small as possible. Both the SPG and MLP SPG frequently arise in network design and wiring layout problems. In this thesis we present two heuristic algorithms for solving the SPG and MLP SPG, respectively. The first algorithm, called 'Shrubbery', aims to find a Steiner tree in a graph with minimum total edge weight. The second algorithm, called 'Pole-Center' ('PC '), aims to minimize two objectives: total edge weight, and the length of the longest path between any two terminals within the tree. We also propose a local search algorithm, called 'Insertion with Two Objectives' ('ITO'), to further improve the quality of the trees produced by PC. (Abstract shortened by UMI.)



Steiner tree Problem in a Graph, minimum-cost tree, terminal vertices, graph, Minimum Longest-Path SPCA, Shrubbery, Pole-Cente, edge weight, longest path, Insertion with Two Objectives