Re: [algogeeks] min no of policemen
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 ), min_police(root,true) + 1) /* r - root of the subtree we're solving for covered - a flag denoting whether the current node contains a police */ *min_police( r, covered ) : result = 0 /* the current node contains the police man so the adjacent nodes may / may not have a police man. */ if( covered ) for each vertex v1 adjacent to r do result = result + minimum ( min_police(v1, false), min_police(v1,1) + 1 )* *return result else /* -current node doesn't contain a police man so at least one of the adjacent nodes must have a police man. - we initially find the minimum number of police men by not considering the above restriction - if in the process of greedily assigning policemen we had assigned a policeman to one of the adjacent nodes then we do nothing - otherwise we need to assign policeman to the node where the difference between number policemen in two cases is least. */ min_c_diff = int_max min_c_dif_node = -1 **for each vertex v1 adjacent to r do c1 = min_police( v1,false) c2 = min_police(v1,1) + 1 if c1 c2 if min_c_diff c2-c1 min_c_diff = c2-c1 min_c_diff_node = v1 result = result + minimum ( c1,c2 )* * if min_c_diff 0: result = result - min_c_diff* *return result** * I have not included the Dynamic programming or Memoization part here but you can extend the idea and implement it. And what you have asked is the special case of a general problem Vertex Cover in a graph. http://en.wikipedia.org/wiki/Vertex_cover It is considered NP-complete for general graphs. But for the trees it can be solved in O(|V|) using the above explained algorithm. Hoping it helps. On Tue, Jun 8, 2010 at 9:08 PM, Raj N rajn...@gmail.com wrote: @sharad: Can u explain topological sort here? On Tue, Jun 8, 2010 at 12:06 PM, divya jain sweetdivya@gmail.comwrote: @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, divya sweetdivya@gmail.com wrote: 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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this
Re: [algogeeks] min no of policemen
@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, divya sweetdivya@gmail.com wrote: 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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] min no of policemen
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 sweetdivya@gmail.com wrote: 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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] min no of policemen
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 total number of nodes ((2^(h+1) -1)-2^h On Mon, Jun 7, 2010 at 10:53 PM, Anurag Sharma anuragvic...@gmail.comwrote: 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 sweetdivya@gmail.com wrote: 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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] min no of policemen
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 can use bellman ford bfs.or even make use of topological sort. On Mon, Jun 7, 2010 at 9:59 PM, divya sweetdivya@gmail.com wrote: 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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] min no of policemen
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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
