2008 · 10 citations · 5 references
ComputingComputer ScienceComputer SystemsAlgorithmsComputer NetworksFault-tolerant SystemsCombinatorial OptimizationDistributed ComputingDynamic ProgrammingEdge ReliabilityNetwork Fault ToleranceNetwork ReliabilityMulticast RoutingNetwork Reliability AlgorithmsPolynomial Time ComplexityPolynomial-time AlgorithmsReliable MulticastService Station PlacementTree AlgorithmsTree Networks
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.
5
On multicast path finding algorithms
C.-H. Chow · 1991 · 91 citations
An O(n log n) algorithm for maximum st-flow in a directed planar graph
2006 · 27 citations