Given a un-directed weighted graph G=(V,E) where V is the set of vertices and E is the set of edges between vertices, and weights are the time delays on each link between two user. The goal is to construct a multicast tree T (that connects source node to a set of nodes say K) such that to minimize the maximum (longest) delay of the last user in the multicast tree T. The maximum (longest) delay of the multicast tree T should be less than or equal to say d. Thus it seems a an NP-Complete problem but I don't know how to prove it or reduce it. I will appreciate your kind feedback. Thank you
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Refer to Shorted Path Tree (SPT)- https://en.wikipedia.org/wiki/Shortest-path_tree It ensures that the delay from source node is always minimum for all the nodes including the maximal ones.
Based on your problem description I think it is SPT. If that's the case, it is not a $\text{NP}$-hard problem.
