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