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 triangleor cycle of length 3.

  1. 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
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: