Coreman :Graph Algorithms

Question

The square of a directed graph G=(V,E) is the graph G2=(V,E2) such that
(u,v) ∈ E2 if and only G contains a path with at most two edges between u and v.
Describe efficient algorithms for computing G2 from G for both the adjacency-list
and adjacency-matrix representations of G. Analyze the running times of your
algorithms.

Answer 1

Adjacency list

If we are given the adjacency list representation of G then we compute the adjacency list representation of transpose of G. This would take O (V+E) time. Now to compute the adjacency list of G-square we first scan through the adjacency list of each vertex in G. Suppose we are scanning the adjacency list of vertex v of graph G. If u belongs to the adjacency list of v then u is also added in the adjacency list of v in G-square.Now we scan through the adjacency list of v in G-transpose. Suppose the list contains the vertices u1,u2,...un. Then u is added to the adjacency list of u1,u2,...,un in G-square. In this way we form the adjacency list of G-square. This would take O(|V||E|+|V|) time because we have to spend |V| time when we process through each edge.

Adjacency matrix 

The time complexity is written wrong it will be O(V3)

Comments

thank you for answering...You only wrote about adjacency matrix ..can u tell me about adjacency list??

---

Answer edited

---

Thank you for the detailed explanation.