see it works when we apply
BFS we get
1
4 2 7
8 6
5
3
when we apply dfs we get
1
4
3
2
8
5
6
7
so on dfs we get nodes
as 1,3,8,6
and on bfs we get
1,3,8,6
so independent set is 1,3,8,6 which is same as fig 2 of site
http://en.wikipedia.org/wiki/Maximal_independent_set
i guess i will have to find a way how do i use it so that i can get a
maximal independent set perfectly ): in not exponentional time
On Mon, May 2, 2011 at 9:43 PM, prajay shetty <[email protected]>wrote:
> ya it works on independent set but will try it for maximal indpendent set.
> i guess it will fail if it fails back to drawing room );
>
>
> On Mon, May 2, 2011 at 9:24 PM, Rahul Gulati <[email protected]>wrote:
>
>> Okay! Try this - Write a brute force program that can find the maximal
>> independent for say a graph of size 20. Create a test file (some 50 - 100
>> random testcases). Test the outputs of the brute force program with that of
>> your algorithm. You'll find the bugs/corner-cases.
>>
>> Regards,
>>
>> Rahul
>>
>>
>> On Mon, May 2, 2011 at 9:20 PM, prajay shetty
>> <[email protected]>wrote:
>>
>>> ya it does because see here
>>>
>>> http://en.wikipedia.org/wiki/Complete_graph
>>>
>>> considering this
>>>
>>> if u apply a dfs on this on k=10
>>> dfs will travel all long 1,2,3,4,5
>>>
>>> now when we apply bfs we will get it as
>>> 1
>>> 2 3 4 5
>>>
>>> so all 2,3,4,5 will get eliminated since all are connected to the nodes
>>> marked as yellow and if u select a node it will give u 1 then all gets
>>> eliminated ie 2 ,3,4,5
>>>
>>> thanks rahul for your question
>>>
>>>
>>> On Mon, May 2, 2011 at 9:12 PM, Rahul Gulati <[email protected]>wrote:
>>>
>>>> Try out some corner cases like complete graphs, etc. Does your algorithm
>>>> return 1 for a complete graph?
>>>>
>>>> On Mon, May 2, 2011 at 9:09 PM, prajay shetty <[email protected]
>>>> > wrote:
>>>>
>>>>> thanks for the admin coorporation please post the problem
>>>>>
>>>>>
>>>>> On Mon, May 2, 2011 at 8:19 PM, prajay shetty <
>>>>> [email protected]> wrote:
>>>>>
>>>>>>
>>>>>> Hey all,
>>>>>>
>>>>>> Last week i was going trough corfment this is not a gcj problem but i
>>>>>> had wrote an algorithm on np complete that is an independent set problem
>>>>>> which has no cycle and no weight i had tried this algorithm on this type
>>>>>> of
>>>>>> graphs , can anyone provied me with counter example if any ,I taught this
>>>>>> was the good one comunicate with you members since most of you will be
>>>>>> good
>>>>>> at DSA atleast more than me ): thanks for any help in the problem
>>>>>>
>>>>>> so here is our graph which has following properties as an example
>>>>>> 1) node 1 is connected to node 2
>>>>>> 2) node 2 is connected to node 3
>>>>>> 3) node 3 is connected to node 1
>>>>>> 4)node 2 is connected to node 5
>>>>>> 5) node 2 is connected to node 4
>>>>>> 6) node 5 is connectd to node 6
>>>>>> 7)node 4 is connected to node 5
>>>>>> 8) node 3 is connected to node 7
>>>>>> 9) node 7 is connected to node 8
>>>>>> 10) node 8 is connected to node 3
>>>>>>
>>>>>>
>>>>>> First by seeing the graph we have independent set is 1,4,6,8
>>>>>> Algorithm
>>>>>>
>>>>>> 1)We genearte dfs on graph g
>>>>>> 2) We genearte bfs on g
>>>>>> 3)DFS: here we modify our dfs a bit insteda as we go through dfs we
>>>>>> color first node as blue and we dont color the next node and we color
>>>>>> the
>>>>>> next node blue this continues till we reach a dead end.,we list all the
>>>>>> node that we marked as blue.
>>>>>> for example we get the output as 1,3,5 now we explore 3 and we dont
>>>>>> color 7 and then we color 8 like this we procceed, output is 1,3,4,6,8
>>>>>> 4) BFS: we generate bfs, then once we got the list of nodes we
>>>>>> maintain a pair node in an array as parent child in our array for
>>>>>> example we
>>>>>> store 1->2,3 and 2->4,5 and 3->7,8 for bfs we can just reduce the memory
>>>>>> space by working on efficient ds on this.
>>>>>> 5) then we color all the node as yellow in our bfs tree for the nodes
>>>>>> that we obtain in step 3
>>>>>> 6)now we check if the node that is in the list has a node connected
>>>>>> to it colored as yellow ,if yes we delete it from our final list and in
>>>>>> this way we get we remove 3 as 3 is connected to 1
>>>>>> so we get our final list as 1,4,6,8
>>>>>>
>>>>>> just want to check if there is any counter example for this ...thanks
>>>>>> for your help
>>>>>>
>>>>>>
>>>>>> Note: step 3 can be done with step 1 and step 2 can be done with step
>>>>>> 4
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Regards ,Prajay
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Regards ,Prajay
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "google-codejam" 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/google-code?hl=en.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Rahul Gulati
>>>> [email protected]
>>>> Department of Computer Science
>>>> Jaypee Institute of Information Technology (Deemed University)
>>>> India
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "google-codejam" 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/google-code?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> Regards ,Prajay
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "google-codejam" 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/google-code?hl=en.
>>>
>>
>>
>>
>> --
>> Rahul Gulati
>> [email protected]
>> Department of Computer Science
>> Jaypee Institute of Information Technology (Deemed University)
>> India
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "google-codejam" 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/google-code?hl=en.
>>
>
>
>
> --
> Regards ,Prajay
>
--
Regards ,Prajay
--
You received this message because you are subscribed to the Google Groups
"google-codejam" 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/google-code?hl=en.
