Problema de Steiner em Grafos: Algoritmos Primais, Duais e Exatos. Master's Thesis, Department of Informatics, PUC-Rio, 2001 (in Portuguese).
(Title in English: Steiner Problem in Graphs: Primal, Dual, and Exact Algorithms.)

Abstract: The Steiner problem in graphs is one of the most important NP-hard problems in combinatorial optimization, with applications in VLSI design, networks, logistics and computational biology, among others. We present a computational assessment of several strategies to deal with this problem in practice. The methods are divided into a number of classes: constructive heuristics, local search procedures, metaheuristics, dual heuristics and exact algorithms. Each class has its own way of dealing with the problem: running times, solution qualities and guarantees provided differ among them. We discuss the most relevant algorithms described in the literature and propose new ones. The result is a collection of tools that represent the state-of-the-art in practical algorithms for the Steiner problem in graphs. Several open instances in the literature were solved or had their bounds improved by these methods.