Maximum reliability k-hop multicast strategy in tree networks

Abstract

In this paper we consider directed tree networks, for which the reliability of each edge (a real number between 0 and 1) is known. For these networks, we investigate the problem of finding a k-hop multicast strategy of maximum reliability. This problem is equivalent to the k-station placement problem, which was previously solved in polynomial time for trees. We present here O(kldrn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) and O(kldrn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) dynamic programming algorithms for the problem, which improve upon the previous best known solution, which is O(kldrn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ldrlog(n)) and rather complicated to implement. We then extend the algorithms to general directed graphs and also present some new algorithms for this case.