Consider the problem of determining whether an undirected graph G = (V, E) conta

Question

Consider the problem of determining whether an undirected graph G = (V, E) contains a triangle (cycle of length three). (a) Give an 0(|V|^3) to find a triangle if one exists. (b) Improve your algorithm to run in time O(|V| middot |E|). You may assume |V| lessthanorequalto |E|. You are given a weighted graph and its minimum spanning tree. There are n vertices and m edges in the graph. (a) Design a polynomial-time algorithm that finds the smallest change in the weight of a non-MST edge that would cause a change in the MST. (b) Analyze the runtime of your algorithm in terms of n and m.

Explanation / Answer

4a) Let A[][] be adjacency matrix representation of graph if not it can be converted to adjacency matrix representation in O(V2) time. If we calculate A3 and observe the trace elements of the resulting matrix, if any one of them is non-zero, then the graph has a triangle otherwise no triangle. This works because  In A3, we get all distinct paths of length 3 between every pair of vertices. Since we are interested in paths that start and end at same point, we will look at trace elements,

The time complexity will be O(V3) for computing A3 and going through trace elements.

4b)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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