A note on line broadcast in digraphs under the edge-disjoint paths mode

AbstractIt is known that unless NP⊂DTIME(nloglogn), no polynomial-time approximation algorithm for the multicast problem can have approximation ratio less than Ω(logn) in n-node digraphs under the edge-disjoint paths mode of the line model. In this note, we give a polynomial-time O((Δmin+logn)/(log(Δmin+logn)))-approximation algorithm, where Δmin is the smallest integer k such that there exists a rooted directed tree of maximum out-degree k, spanning the considered digraph