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 <[email protected]> wrote:
> @sharad: Can u explain topological sort here?
>
>
> On Tue, Jun 8, 2010 at 12:06 PM, divya jain <[email protected]>wrote:
>
>> @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 <[email protected]> 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 <[email protected]> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected]<algogeeks%[email protected]>
>>>> .
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
