@Nagendra: I think thats exactly what needs to be done. Triangle is a 3-clique.
Not sure if the interviewer had the same definition in mind. @Ankur: Please comment. _dufus On Sep 7, 8:25 pm, Nagendra Kumar <nagendra....@gmail.com> wrote: > is it not finding a cycle in a graph of length 3. > > On Sun, Sep 6, 2009 at 9:02 PM, Dufus<rahul.dev.si...@gmail.com> wrote: > > > The following approach might work. > > Let K be the maximum degree of a vertex in the graph > > Enumerate each of the n vertex as 1...n > > Enumerate undirected edge between vertex i and j (i.e. i------j) as > > (i,j) > > > Sort all the |E| edges in O(|V| + |E|) time // radix sort. > > Now (i1,i2,i3) form a triangle iff there exist edges > > (i1,i2) > > (i1,i3) > > (i2,i3) > > > For any vertex i1 we need to check C(k,2) pair of vertices {(i1,i2), > > (i1,i3)} > > By maintaining a hash table we can check if edge exists between > > (i2,i3) in O(1) time. > > > Hence we can determine 3-clique from sorted list in (V.C(k,2)) time > > which is O(|E|) if k=O(n) or O(|V|) if k=O(1) > > > Hence we can determine all the triangles in O(|V| + |K|) time and O(| > > E|) space. > > > _dufus > > > On Sep 6, 2:28 pm, ankur aggarwal <ankur.mast....@gmail.com> wrote: > >> google question : find triangle in a graph Given an undirected graph, > >> design a O(V+E) algo to detect whether there is a triangle in the graph ot > >> not. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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 -~----------~----~----~----~------~----~------~--~---