Problem 4. (15 marks) Given an undirected graph G = (V, E), the square of it is

Question

Problem 4. (15 marks) Given an undirected graph G = (V, E), the square of it is the graph G-X, E?) such that for any two nodes u, u V, {u,r) if and only if the distance between u and u in G is at most 2, i.e., u,v E E or there is a wE V such that (u, wj,w,v E E. (Therefore, it is clear that any e E E will remain an edge also in E2.) a. (7 marks) Propose an algorithm that takes as an input a graph G with a max-degree of in the adjacency list model and outputs G2 in O(A2n)-time, and prove the running time of your algorithm. b. (8 marks) Propose an algorithm that takes as an input a graph G in the adjacency matriz model and outputs G2 in o(n3)-time. Prove the correctness and running time of your algorithm. (Hint: Wec t an adjacency matriz for a reason..)

Explanation / Answer

A)Algorithm:

Adjacency list of G to G^2 then

for every vertex vp G// run n times

for every vertex vj adj(vp) // run delta times

for every vertex vj adj(vp) // run delta times

add vk to adj(vp) of G^2

end

end

end

proof:

* Length of the adjacency list of every vertex

* In this above algorithm use three loops

* first one run n times

* innner loop will run times

* another loop will also run times

Run time can be O(^2 n)

B) Algorithm:

where M is the adjacency matrix of G Graph

where M^2 is the adjacency matrix of G^2 graph

for i 1=1 to num

for j 1=1 to num

for k 1=1 to num

if M[i][k!]==1 and M[k1][j1]==1

M^2[i][j1]=1

end

end

end

Run time:

Any graph has n verticees running for three loops

Complexity O(n^3)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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