# Problem: Let G=(V,E) be a connected graph and v be a node of G. The eccentricity e(v) of v is the…

Problem:

Let G=(V,E) be a connected graph and v be a node of G. The eccentricity e(v) of v

is the distance to a node farthest from v. Thus:

e(v) = max {d(u,v): u ?V}

where d(u,v) is the shortest distance from v to u.

The radius R(G) is the minimum eccentricity of the nodes, whereas the diameter

D(G) is the maximum eccentricity. Node v is a central node if e(v) = R(G), it is a

peripheral node if e(v) = D(G).

In the following, we assume that G is a weighted graph, n = |V|, and e = |E|.

1- In this part, we assume that the weights are any positive integer:

a) Give an algorithm that finds the set of central nodes and the set of peripheral nodes

in G.

b) Give the time complexity of your algorithm.

2- In this part, we assume that the weights are equal:

a) Give an O(e) single source shortest path algorithm.

b) Using the algorithm in part 1-a, write an algorithm to find the set of central nodes

and the set of peripheral nodes in G. Analyze the time complexity of your algorithm.