Question: Tamarindo University and many other schools worldwide are doing a joint project on multimedia. A computer network is built to connect these schools using communication

Tamarindo University and many other schools worldwide are doing a joint project on multimedia. A computer network is built to connect these schools using communication links that form a free tree. The schools decide to install a file server at one of the schools to share data among all the schools. Since the transmission time on a link is dominated by the link setup and synchronization, the cost of a data transfer is proportional to the number of links used. Hence, it is desirable to choose a “central” location for the file server. Given a free tree T and a node v of T, the eccentricity of v is the length of a longest path from v to any other node of T. A node of T with minimum eccentricity is called a center of T. 

a. Design an efficient algorithm that, given an n-node free tree T, computes a center of T. 

b. Is the center unique? If not, how many distinct centers can a free tree have?

Step by Step Solution

3.40 Rating (162 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock

a No Not always unique Its possible that the remaining tree has two nodes Consider a... View full answer

blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Data Structures Algorithms Questions!