Home
> Uncategorized > Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3

## Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3

Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3.

Give o(v^3) algorithm for it.

Solution:

step 1: Run DFS on the given as it is.

step 2: In the DFS-visit of vertice ( say u ) run a modified BFS ( say BFS2).

The algorithm for BFS2 is as following:

BFS2(u) { foreach v1 belongs to adj[u] foreach v2 belongs to [adj[v1] - u] { // because we know u must be adjacent of v1. that's why we will not let u create massacre here. if ( v2 and u are adjacent to each other ) Report ( u,v1,v2) as a cycle or length 3 . } }

This problem appears in algorithm design manual by skiena as following

5-17. Consider the problem of determining whether a given undirected graph *G* = (*V*,*E*) contains a *triangle*or cycle of length 3.

- Give an
*O*( |*V*|^{3}) to find a triangle if one exists.

The complexity id v3 because for each vertices BFS2 will run for with v^2 complexity.

Advertisements

Categories: Uncategorized

Comments (0)
Trackbacks (0)
Leave a comment
Trackback