In an adjacency list representation of an undirected simple graph \(G =…

GATE · 2016 · CS · Set 2 · Computer Science & IT

In an adjacency list representation of an undirected simple graph G=(V,E)G = (V,E), each edge (u,v)(u, v) has two adjacency list entries: [vv] in the adjacency list of uu, and [uu] in the adjacency list of vv. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |EE| = mm and |VV| = nn, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

  1. A.

    Θ(n2)Θ(n^2)

  2. B.

    Θ(n+m)Θ(n+m)

  3. C.

    Θ(m2)Θ(m^2)

  4. D.

    Θ(n4)Θ(n^4)

Attempted by 460 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…