Definition and algorithms for reliable steiner tree problem

This paper considers a new form of the Steiner tree problem that is more practical and reliable, which we call Reliable Steiner Tree (RST) problem. The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it. The definition is based on the reliability of full components instead of Steiner vertices. The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree. The exact algorithm designed for this problem utilizes a dynamic programming frame. The approximationalgorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.