Maximum reliability k-hop multicast strategy in tree networks
Mugurel Ionuţ Andreica, Nicolae Ţăpuş · 2008
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(kldrn2) and O(kldrn3) dynamic programming algorithms for the problem, which improve upon the previous best known solution, which is O(kldrn2ldrlog(n)) and rather complicated to implement. We then extend the algorithms to general directed graphs and also present some new algorithms for this case.