A Little late in replying but:
This can be solved using *Dynamic programming* or Memoization in O( |V| )
|V| - Number of nodes in the tree.
Here is the rough idea of the algorithm:
Step1: Arbitrarily select a node of the tree as root.
Step2: result = minimum( min_police( root, false ),
@sharad..
sorry bt i dint get how to use bellman ford or topological sort here...
can u plz explain...
On 8 June 2010 05:53, sharad kumar aryansmit3...@gmail.com wrote:
for placing police man we can use bellman ford bfs.or even make use of
topological sort.
On Mon, Jun 7, 2010 at 9:59 PM,
Can you expain edge of the tree. I could not get that.
Anurag Sharma
On Tue, Jun 8, 2010 at 5:53 AM, sharad kumar aryansmit3...@gmail.comwrote:
for placing police man we can use bellman ford bfs.or even make use of
topological sort.
On Mon, Jun 7, 2010 at 9:59 PM, divya
Min number of police man could be placed on the nodes which does not have
leaf nodes.
Only things needs to find out is the height of the tree.O(logn).
For any given tree: 1. calculate the leaf node: 2^h (h is the height of
the tree)
2. Subtract leaft nodes from the
edge is the link connecting two nodes of a tree
On 8 June 2010 11:23, Anurag Sharma anuragvic...@gmail.com wrote:
Can you expain edge of the tree. I could not get that.
Anurag Sharma
On Tue, Jun 8, 2010 at 5:53 AM, sharad kumar aryansmit3...@gmail.comwrote:
for placing police man we
consider a tree. policemen is to be placed such that for each edge of
tree, there is a policeman on atleast one side of each edge. tell the
min no. of policemen and their locatn in time O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
