6.5.4 Center Problems

Example 17: Locating a Firehoase in a Ruwral Area

Consider the graph shown on Figure 6.37 which depicts a rural area with five towns, shown as nodes A through E, connected by a rather sparse transportation network with link lengths in miles also indicated. Town populations in thousands are listed in parentheses next to each node.

The towns have entered into a cooperative agreement to obtain joint fire protection for certain types of fires. They are planning to build a firehouse where a single special, purpose fire engine, yet to be purchased, will be stationed. A considerable amount of discussion has led to the conclusion that the location of the firehouse must be such as to minimize the farthest distance that the fire engine will ever have to travel in responding to a fire alarm. This, indeed, is a quite reasonable objective for an emergency-type service such as the fire department.

Suppose, first, that the location of the firehouse were restricted to be at one of the five cooperating towns. By first obtaining the minimumdistance matrix [d(i, j)] for the given network and then by choosing the row with the minimum maximum entry, we can find the node that minimizes the maximum distance to all other nodes. This procedure is shown in Table 6-10. The optimum location for the facility is town C with a maximum distance of 3 miles to both town A and town E.

Then let us ask whether the unrestricted optimum location for the firehouse is also on node C. That is, if we are free to locate the firehouse at any point at all on the network, will it still be located at town C?

This turns out to be a rather difficult question to answer. We shall do this after introducing a convenient notation and some definitions.

Let G(N, A) be an undirected network. (Entirely similar concepts with some minor modifications to account for link directivity apply to directed networks.) Let x G be any point on the network. Then, we denote the distance between x and the node of G which is farthest away from it as

With reference to our last example, we have already found the vertex center of the graph of Figure 6.37 to be at node C. We now wish to find the absolute center of that graph.

An algorithm for finding the absolute center of an undirected graph G can be simply described as follows.

Single-Center Algorithm (Algorithm 6.12)

STEP	1:	For each link of G. find the local center x of .
STEP	2:	Among all the local centers x , choose the one with the smallest m(x). That local center is also the absolute center x* of G.

Unfortunately, Step 1 of this simple two-step algorithm is a time-consuming one. We illustrate this through our earlier example.

Example 17 (continued)

To find all the local centers on the graph of Figure 6.37, we examine each of the five network links separately. The procedure is described in pictorial form in Figure 6.38.

Consider, for instance, the link (A, B) with a length of 4 units. For all points x on (A, B) we can find and plot the functions d(x, j) for j = A, B. C, D, E. For instance, if we set, by convention, x = 0 at A and x = 4 at B. we have

The functions d(x, A), d(x, B), d(x, C), d(x, D), and d(x, E) are all shown on Figure 6.38a for the link (A, B). Now, since, by definition,

the function m(x) is given by the upper envelope for the five functions as shown on Figure 6.38a. Obviously, the local center of link (A, B) is at a point 0.5 unit away from A (and 3.5 units away from B) and m(x) = 3.5.

Repeating the same procedure for the other four links, we finally obtain

link (A, B): local center 0.5 unit from A; m(x) = 3.5

link (A, D): local center at A and at D; m(x) = 4

link (B. C): local center at C; m(x) = 3

link (D, E): local center at D; m(x) = 4

link (C, D): local center 0.5 unit from C; m(x) = 2.5

This completes Step 1 of the algorithm. In Step 2 we choose the point x^* on the link (C, D) and 0.5 unit away from C for the location of the absolute center; m(x^*) = 2.5.

From our example we conclude that:

1.	The absolute center and the vertex center do not have to coincide. In fact, the absolute center does not have to be on a link emanating from the node where the vertex center is located--as was the case in our example.
2.	The maximum distance function, m(x), is piecewise linear and its slope is always +1 or -1.

From the second remark above, the following result can be easily derived [ODON 74]:

Theorem: For the local center, x, on a link (p, q),

Exercise 6.7 Prove the validity of the theorem.

From this theorem and from the observation that, by definition, m(i^*) m(x^*) (i.e., the maximum distance associated with the vertex center must be greater than or equal to the corresponding distance for the absolute center), we can derive the following simple test:

If for a link (p, q),

then the local center x of (p, q) cannot improve on m(i^*) (and, therefore, need not be found).

This test, taking advantage of the fact that it is very simple to find m(i^*), often leads to considerable reduction in the computation effort required to obtain the absolute center (see also Problem 6.12).

Example 17 (continued)

With respect to our five-node, five-link example we found easily that the vertex center is at node C and that m(i^*) = m(C) = 3.

Applying our test to the five links of the graph, we then obtain

Therefore, the local center need be found only for links (A, B) and (C, D)--a significant savings in computational effort.

We also note that a highly efficient algorithm exists for finding the absolute center when the network at hand happens to be a tree (see Problem 6.11). The algorithm [HAND 73] is the following:

Single-Tree-Center Algorithm (Algorithm 6.13)

STEP	1:	Choose arbitrarily any point x G and find the (end) vertex, say es, farthest away from x.
STEP	2:	Find the (end) vertex, say et, which is farthest away from es.
STEP	3:	The absolute center of G is at the midpoint of the path from es to et . The vertex center of G is at the node that is closest to the absolute center.

This last algorithm does not even require computing the minimum distance matrix for the tree network G!