An approach for the Steiner problem in directed graphs (Q1179756)

The authors present a scheme to solve Steiner problems in directed graphs using a heuristic method to obtain upper bounds and the \(k\) shortest arborescences algorithm to compute lower bounds. They combine these ideas in an enumerative algorithm. The approach is based on both a ranking algorithm to find lower bounds and an improved version of the Wong algorithm to find upper bounds. Computational results are presented for both the \(k\) shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.