An approach for the Steiner problem in directed graphs

The authors present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and the k shortest arborescences algorithm to compute lower bounds. They propose to combine these ideas in an enumerative algorithm. Computational results are presented for both the k shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.