A partition-based heuristic for the steiner tree problem in large graphs

Markus Leitner, Ivana Ljubić, Martin Luipersbeck, Max Resch

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


This paper deals with a new heuristic for the Steiner tree problem (STP) in graphs which aims for the efficient construction of approximate solutions in very large graphs. The algorithm is based on a partitioning approach in which instances are divided into several subinstances that are small enough to be solved to optimality. A heuristic solution of the complete instance can then be constructed through the combination of the subinstances' solutions. To this end, a new STP-specific partitioning scheme based on the concept of Voronoi diagrams is introduced. This partitioning scheme is then combined with state-of-the-art exact and heuristic methods for the STP. The implemented algorithms are also embedded into a memetic algorithm, which incorporates reduction tests, an algorithm for solution recombination and a variable neighborhood descent that uses best-performing neighborhood structures from the literature. All implemented algorithms are evaluated using previously existing benchmark instances and by using a set of new very large-scale real-world instances. The results show that our approach yields good quality solutions within relatively short time.

Original languageEnglish
Title of host publicationHybrid Metaheuristics - 9th International Workshop, HM 2014, Proceedings
PublisherSpringer - Verlag
Number of pages15
ISBN (Print)9783319076430
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event9th International Workshop on Hybrid Metaheuristics, HM 2014 - Hamburg, Germany
Duration: 11 Jun 201413 Jun 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8457 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference9th International Workshop on Hybrid Metaheuristics, HM 2014


Dive into the research topics of 'A partition-based heuristic for the steiner tree problem in large graphs'. Together they form a unique fingerprint.

Cite this