The time delay of a long-distance call can be determined by multiplying a small fixed constant by the number of communication links on the telephone network between the caller and callee. Suppose the telephone network of a company named RT&T is a free tree. The engineers of RT&T want to compute the maximum possible time delay that may be experienced in a long-distance call. Given a free tree T, the diameter of T is the length of a longest path between two nodes of T. Give an efficient algorithm for computing the diameter of T.

Question

Phoenix Kim

Computers & Technology

1 July, 12:35

The time delay of a long-distance call can be determined by multiplying a small fixed constant by the number of communication links on the telephone network between the caller and callee. Suppose the telephone network of a company named RT&T is a free tree. The engineers of RT&T want to compute the maximum possible time delay that may be experienced in a long-distance call. Given a free tree T, the diameter of T is the length of a longest path between two nodes of T. Give an efficient algorithm for computing the diameter of T.

+5

Answers (1)

Know the Answer?

Camille Trujillo · Answer 1

The diameter of T is 2k+1.

See explaination for the details

Explanation:

We can compute the diameter of the tree T by a pruning procedure, starting at the leaves (external nodes).

Remove all leaves of T. Let the remaining tree be T1.

Remove all leaves of T1. Let the remaining tree be T2.

Repeat the "remove" operation as follows: Remove all leaves of Ti. Let remaining tree be Ti+1.

When the remaining tree has only one node or two nodes, stop! Suppose now the remaining tree is Tk.

If Tk has only one node, that is the center of T. The diameter of T is 2k.

If Tk has two nodes, either can be the center of T. The diameter of T is 2k+1.