ZuoTi.Pro
Question

Suppose you are given an undirected graph G. Find a pair of vertices (u, v) in G with the largest number of common adjacent vertices (neighbors). Give pseudocode for this algorithm and show the worst-case running time.

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Following algorithm is based on adjacncy matrix representation of graph.

find_pair(u,v,G)

n←G[V]

    max,count←0

    I,j,k←0

    Visited[n],adj[n][n]

  Loop for(i=0;i<n;i++)

                 Visited[i] ←0

    Loop:   for(i=0;i<n;i++)

                 Loop: for(j=0;j<n;j++)

                             if(adj[i][j]=1&&Visited[j]=0)

                                count++;

                                 loop: for(k=0 ;k<n;k++)

                                           if(adj[i][k]=adj[j][k]

                                         count++;

                                if(count>max)

                                      u←i

                                     v←j

                           

                                  count←0

                     Visited[i] ←1

        

Time complexity of algorithm is O(n2)

0 0
Add a comment
Know the answer?
Add Answer to:
Suppose you are given an undirected graph G. Find a pair of vertices (u, v) in...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Reachability. You are given a connected undirected graph G = (V, E ) as an adjacency...

    Reachability. You are given a connected undirected graph G = (V, E ) as an adjacency list. The graph G might not be connected. You want to fill-in a two-dimensional array R[,] so that R[u,v] is 1 if there is a path from vertex u to vertex v. If no such path exists, then R[u,v] is 0. From this two-dimensional array, you can determine whether vertex u is reachable from vertex v in O(1) time for any pair of vertices...

  • 2. Let G = (V, E) be an undirected connected graph with n vertices and with...

    2. Let G = (V, E) be an undirected connected graph with n vertices and with an edge-weight function w : E → Z. An edge (u, v) ∈ E is sparkling if it is contained in some minimum spanning tree (MST) of G. The computational problem is to return the set of all sparkling edges in E. Describe an efficient algorithm for this computational problem. You do not need to use pseudocode. What is the asymptotic time complexity of...

  • Consider an unweighted, undirected graph G = 〈V, E). The neighbourhood of a node u E V in the gr...

    This question needs to be done using pseudocode (not any particular programming language). Thanks Consider an unweighted, undirected graph G = 〈V, E). The neighbourhood of a node u E V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v) (a) Design an...

  • Consider an unweighted, undirected graph G = 〈V, E). The neighbourhood of a node u E V in the gr...

    Consider an unweighted, undirected graph G = 〈V, E). The neighbourhood of a node u E V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v) (a) Design an algorithm that returns a list containing the neighbourhood degree for each node v V,...

  • 2. Let G be an undirected graph. For every u,vE V(G), let dc(u,v) be the length of the shoertest ...

    2. Let G be an undirected graph. For every u,vE V(G), let dc(u,v) be the length of the shoertest path from u to v. The diameter of G is he maximum distance bet In other words: max (de(u, v) u,vEV(G) the running time of your algorithm 2. Let G be an undirected graph. For every u,vE V(G), let dc(u,v) be the length of the shoertest path from u to v. The diameter of G is he maximum distance bet In...

  • A 2-coloring of an undirected graph with n vertices and m edges is the assignment of one of two colors (say, red or green) to each vertex of the graph

    A 2-coloring of an undirected graph with n vertices and m edges is the assignment of one of two colors (say, red or green) to each vertex of the graph, so that no two adjacent nodes have the same color. So, if there is an edge (u,v) in the graph, either node u is red and v is green or vice versa. Give an O(n + m) time algorithm (pseudocode!) to 2-colour a graph or determine that no such coloring...

  • Question 1: Given an undirected connected graph so that every edge belongs to at least one...

    Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so...

  • Problem 1: Given a graph G (V,E) a subset U S V of nodes is called...

    Problem 1: Given a graph G (V,E) a subset U S V of nodes is called a node cover if each edge in E is adjacent to at least one node in U. Given a graph, we do not know how to find the minimum node cover in an efficient manner. But if we restriet G to be a tree, then it is possible. Give a greedy algorithm that finds the minimum node cover for a tree. Analyze its correctness...

  • 3. (10 points) Let G be an undirected graph with nodes vi,..Vn. The adja.- cency matriz represent...

    Please show work clearly. Thanks 3. (10 points) Let G be an undirected graph with nodes vi,..Vn. The adja.- cency matriz representation for G is the nx n matrix M given by: Mij-1 if there is an edge from v, to ty. and M,',-0 otherwise. A triangle is a set fvi, vjof 3 distinct vertices so that there is an edge from v, to vj, another from v to k and a third from vk to v. Give and analyze...

  • The Max Cut problem is given a undirected graph G(V, E), finding a set S so...

    The Max Cut problem is given a undirected graph G(V, E), finding a set S so that the number of edges that go between S and V − S is maximum. This is an NPC problem. a) Show that there is always a max cut of size at least |E|/2. Hint: Decide where to put vertices according to if they have more neighbors in S or V − S.

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT