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 <[email protected]> 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 [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
-~----------~----~----~----~------~----~------~--~---
