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 -- 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.
