0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.