Hmmm.... I think this is exactly the same problem(where k is generailsed) which is(as they claim) NP hard. Any ideas on the second version where the goal is to minimise the duplication of node visits. Probably some combination of dfs and bfs mite be help(directly or annotating the nodes with someuseful tables similar to routers). not sure.
On 3/14/07, Atamurad Hezretkuliyev <[EMAIL PROTECTED]> wrote: > > > On 3/14/07, Arun <[EMAIL PROTECTED]> wrote: > > > > there are some N robots in a field and the physical orientation is > > known(i.e thier location/distance-with-others). a robot can send a > > message at a given time only to 3 of them. > > you have a source robot and u have a message from this source which is > > to be broadcasted to all the robot. how to broadcast so that the total > > distance covered by the messages is minimal. > > > > I'm not sure if i understand your problem but it seems this is > bounded-degree minimum spanning tree > > check this > http://maven.smith.edu/~orourke/TOPP/P48.html#Problem.48<http://maven.smith.edu/%7Eorourke/TOPP/P48.html#Problem.48> > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
