6.12 Speeding up the search for the absolute center In our discussion of the absolutewenter problem, it was pointed out that the quantity

Another bound for m(x) has been developed recently, as follows. For the link (p, q), let r be the farthest node from p (r N) and s the farthest node from q(s N) [i.e., m(p) = d(p, r) and m(q) = d(q, s)]. The quantities that will be used to develop the new bound are d(p, s) and d(q, r). Clearly, the quantity Max [d(x, r), d(x, s)] provides a lower bound on m(x).

a.

Prove the following result: The quantity Max{d(x, r), d(x, s)} may attain at most a single local minimum within (q, p), i.e., excluding the nodes p and q. If such a local minimum exists it is attained at a point x0 E (p, q) which is a distance away from node p along (p, q) and at which the value of Max{d(x, r), d(x, s)} attains the value L2(p, q) is then a lower bound for m(x) for all points x (p, q), excluding the nodes p and q.

b.

Show that L2(p, q) L1(p, q), that is, that L2(p, q) provides a better lower bound and thus a sharper test than L1(p, q) for speeding up the search for the absolute center of a graph.