search
Log In
0 votes
47 views
The square of a directed graph $G=(V,E)$ is the graph $G^2=(V,E^2)$ such that $(u,v) \in E^2$ if and only $G$ contains a path with at most two edges between $u$ and $v$ .Describe efficient algorithms for computing $G^2$ and $G$ for both the adjacency list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
in Algorithms 47 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
59 views
Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in ... have ? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table ?
asked Apr 7, 2019 in Algorithms akash.dinkar12 59 views
0 votes
0 answers
2
59 views
Most graph algorithms that take an adjacency-matrix representation as input require time $\Omega(V^2)$,but there are some exceptions. Show how to determine whether a directed graph $G$ contains a universal link $-$ a vertex with in-degree $|V-1|$ and out-degree $0$ in time $O(V)$ , given an adjacency matrix for $G$.
asked Apr 7, 2019 in Algorithms akash.dinkar12 59 views
0 votes
1 answer
3
96 views
Given an adjacency-list representation of a multi graph $G=(V,E)$, describe an $O(V+E)$ time algorithm to compute the adjacency-list representation of the “equivalent” undirected graph $G’=(V,E’)$ , where $E’$ is consists of the edges in $E$ with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.
asked Apr 7, 2019 in Algorithms akash.dinkar12 96 views
0 votes
0 answers
4
48 views
The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . Describe efficient algorithms for computing $G^T$ from $G$,for both the adjacency list and adjacency matrix representations of $G$. Analyze the running times of your algorithms.
asked Apr 7, 2019 in Algorithms akash.dinkar12 48 views
...