Let G be an undirected graph with n nodes. A triangle in G is a set of three nod

Question

Let G be an undirected graph with n nodes. A triangle in G is a set of three nodes {u, v, w} such that all three edges (u, v), (v, w) and (u, w) are in G. Let N(x) be the number of triangles in G that contain node x.

The matrix A is the adjacency matrix representing graph G. Z = A × A.

Let M(v) = 0 for each node. For each entry in Z where Z(u,v) > 0, if (u,v) is an edge in G, add Z(u,v) to M(u) and to M(v).

For each node, will the resulting value of M(v) computed be equal to N(v)?

How much time is needed for this algorithm?

Explanation / Answer

Solution :

Yes, the resulting value of M(v) computed be equal to N(v). O(mn) time is needed for the algorithm.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.