BEBR 
 
 FACULTY WORKING 
 PAPER NO. 90-1654 
 
 M-median and M-center Problems with 
 Mutual Communication: Solvable Special Cases 
 
 Dilip Chhajed 
 Timothy J. Lowe 
 
 The I 
 
 Unh ■ 
 
 01 U, 
 
 College of Commerce ana business Administration 
 Bureau o* Economic and Business Research 
 University of Illinois Urbana-Champaign 
 
BEBR 
 
 FACULTY WORKING PAPER MO. 90-1654 
 
 College of Commerce and Business Administration 
 
 University of Illinois at (Jrbana-Champaign 
 
 May 1990 
 
 M-median and M-Center Problems with Mutual Communication: 
 Solvable Special Cases* 
 
 Dilip Chhajed 1 
 Timothy J. Lowe 2 
 
 'Department of Business Administration, University of Illinois at Urbana-Champaign, 1206 South 
 Sixth Street, Champaign, IL 61820 
 
 department of Management Science, University of Iowa, Iowa City, IA 52242 
 
 *We would like to acknowledge the helpful comments of Charles Blair, George Monahan, and Rich 
 Wong. 
 
M-median and M-center Problems with Mutual Communication: 
 
 Solvable Special Cases 
 
 Abstract 
 
 In this paper we consider the network version of the m-median problem with 
 mutual communication (MMMC). We reformulate this problem as a graph theoretic node 
 selection problem defined on a special graph. We give a polynomial time algorithm to solve 
 the node selection problem when the flow graph (graph denoting the interaction between 
 pairs of new facilities in MMMC) has a special structure. We also show that with some 
 modification in the algorithm for MMMC, the m-center problem with mutual 
 communication can also be solved when the flow graph has special structure. 
 
Digitized by the Internet Archive 
 
 in 2011 with funding from 
 
 University of Illinois Urbana-Champaign 
 
 http://www.archive.org/details/mmedianmcenterpr1654chha 
 
1. Introduction 
 
 The network version of the m-median problem with mutual communication 
 (MMMC) is to find the location of m new facilities on a network such that the sum of a.) 
 the fixed location cost of each new facility, b.) the cost of interaction between the new 
 facilities and n existing facilities on the network, and c.) cost of interaction between pairs of 
 new facilities is minimized. The existing facilities are located at nodes of the network and 
 the interaction cost between a pair of facilities is a function of the network distance between 
 the facilities. We call the network on which the new facilities are to be located the transport 
 network, T . 
 
 An application of MMMC is the location of several new machine centers in a 
 production area. Material movements are made on a transport network (e.g. network of 
 aisles). Each new machine center will send and/or receive material to/from one or more 
 existing machine centers whose locations on the transport network are known. In addition, 
 each new machine will have material flow interaction with some subset of the other new 
 machines. We assume that the existing machines are located at nodes of the transport 
 network. There is no loss of generality here, since as long as each existing machine is on 
 the network, its location can be declared as a node. We consider problems where the set of 
 possible locations on the network for each new facility is finite. We can also declare these 
 locations as nodes of the network. We also allow for the possibility that the fixed cost (cost 
 term a.) above) of locating a new facility is dependent upon its location. 
 
 In the above machine location example of MMMC (as well as other examples) it is 
 most likely the case that the cost of interaction between certain pairs of facilities will not 
 depend upon the network distance between their locations. This would occur in the above 
 example if there was no material flow between a pair of facilities. In what follows, we say 
 a pair of facilities interacts only if the cost of interaction is a function of the network 
 distance between the facilities. 
 
 Two graphs can be defined which represent the interaction structure. The demand 
 graph , D, is a bipartite graph with node partition {M,N} where set M consists of m nodes 
 
corresponding to the new facilities and set N consists of n nodes corresponding to the 
 existing facilities, and with u e M and i e N, nodes u and i in D are adjacent if and only if 
 new facility u and existing facility i interact The flow graph, G, consists of m nodes, one 
 corresponding to each new facility. Two nodes in a flow graph are adjacent if and only if 
 the corresponding new facilities interact. 
 
 We note that if the demand graph D has no arcs, then (MMMC) is solved by co- 
 locating the n new facilities at a single point on X which minimizes the sum of the fixed 
 location costs for the new facilities. On the other hand if the flow graph, G, has no edges, 
 then (MMMC) decomposes into n single facility location problems on T. The interesting 
 cases of (MMMC) occur when both D and G are non- trivial. 
 
 Most of the literature associated with (MMMC) deals with the case where there are 
 no fixed location cost (a.) above), and where the interaction costs are linear in network 
 distances. Kolen (1982) has shown that the problem is NP-hard, when T is a general 
 network, but is poly normally solvable when X is a tree. Picard and Radiff (1978) also give 
 a polynomial time algorithm for the' problem when X is a tree. Dealing, Francis, and Lowe 
 (1976) have shown that the problem is a convex optimization problem for all data choices if 
 and only if X is a tree. Erkut, Francis, Lowe, and Tamir (1989) consider a constrained 
 version of the problem and make use of separation conditions (Francis, Lowe, and Ratliff , 
 1978) to obtain a mathematical program. The mathematical program is equivalent to the 
 original problem if X is tree; otherwise the solution to the mathematical program provides a 
 lower bound. A computational study of the lower bound vis-a-vis the original problem is 
 given in Erkut, Francis, and Lowe (1988). 
 
 • Xu, Francis, and Lowe (1988) consider the version of (MMMC) where there are no 
 fixed location costs, and the transport network, X, is not necessarily a tree, but X does 
 contain two or more blocks (maximal, nonseparable subgraphs of X). They show that by 
 solving a related problem on a "blocking graph" (which is a tree), information can be 
 obtained which localizes each optimal new facility to some vertex or block of X. The 
 problem then decomposes into a collection of independent problems, one for each 
 localizing block of X. 
 
 In this paper we give a polynomial time algorithm for a special class of network 
 
MMMC problems in which the transport network, T, and the demand graph, D, are general; 
 the interaction costs are general functions of network distances as long as these cost 
 functions are such that node optimality conditions hold, i.e. there is at least one optimal 
 solution in which each new facility is located at a node of the transport network; and the 
 flow graph. G. is series-parallel . If the node optimality property is not valid then our model 
 is useful when a node restricted solution is sought. 
 
 We also consider the m-center problem with mutual communication (MCMC) and 
 show that the algorithm presented for MMMC can be modified to solve special cases of 
 MCMC. 
 
 The plan of the rest of the paper is as follows. In Section 2 we present a 
 formulation of the problem. Then we introduce a graph theoretic Node Selection Problem 
 (NSP) and show how our formulation of MMMC can be transformed to an NSP. In 
 Section 4 we define a series-parallel graph and give an algorithm to solve the NSP when 
 the flow graph is series-parallel. In Section 5 we give a detailed example showing an 
 application of the algorithm. Section 6 extends our analysis to the m-center problem with 
 mutual communication. We close with some concluding remarks. 
 
 2. Formulation 
 
 For clarity of presentation, we will present the formulation where the 
 interaction costs are linear in network distances. However, our complete methodology is 
 applicable for general interaction cost functions of network distances as long as the node 
 optimality property is valid. In addition, for presentation purposes, in this Section we 
 assume that each new facility could feasibly be located at any node of X. The following 
 notation is used in the formulation. 
 
 Notation: 
 
 aui: interaction cost per unit distance between new facility u and existing facility i 
 
 buy- interaction cost per unit distance between new facilities u and v 
 
d(k,r): distance between existing facilities k and r computed on the transport network 
 
 D: demand graph 
 
 fuk: fixed cost of locating facility u at node k 
 
 G: flow graph (V(G), E(G)). V(G) ={ l,...,m}, E(G)={(u,v): new facilities u 
 
 and v interact, i.e b uv > 0} 
 
 M: set of new facilities 
 
 m: number of new facilities 
 
 N: set of existing facilities 
 
 n: number of existing facilities = I V(T)I 
 
 p,k,r,i: indices of existing facilities 
 
 X: transport network 
 
 u,v: indices of new facilities 
 
 Xuk: {0,1 } variable which takes value 1 if and only if new facility u is located at 
 
 existing facility k 
 
 As mentioned in the introduction, we assume the problem is such that the node 
 optimality condition holds or the solution sought is node restricted. Thus each new facility 
 has to be located at one of the nodes of X. To avoid notational difficulties, we assume 
 without loss of generality that each node of X is the site of an existing facility. If in an 
 application of (MMMC) there is no existing facility at some node, we assume the data 
 consists of a dummy existing facility at the node which has no interaction with any of the 
 new facilities. 
 
 The condition that an arbitrary new facility u must be located at a node of X (site of 
 an existing facility) can be represented by the constraint 
 
 XkeNX u lc= 1 V ueM. (1) 
 
 Given that (1) holds, and the Xuk's are 0,1 variables, (2), (3), and (4) below are valid. The 
 interaction cost between new facility u and existing facility i is given by 
 
 a u ilke N d(i,k) x uk . (2) 
 
 The cost of interaction between two new facilities, u and v, is given by 
 
 buvXre N^ke N XukX V r d(k,r), (3) 
 
and finally, the fixed cost of locating new facility u is 
 
 IkeNfukXuk- ^ 
 
 Summing (2) over all pairs of new and existing facilities, (3) over all pairs of existing 
 
 facilities, and (4) over all new facilities we get the total cost: 
 
 Sue NlXie N a u iXke N d(i,k) Xuk + X U e Mlv(>u)e M b uv Xre N^ke N XukXvr d ( k ' r ) 
 
 + Z U e M^ke N fuk Xuk- (5) 
 
 The first and the last term of (5) can be combined to give 
 
 Sue M^ke N { [Xie N a u i d(i,k)] + fuk } x u k 
 
 = lueMlkeN FukXuk , where Fuk = [lieN a u i d(i,k)] + fuk- 
 
 Thus, Fuk is the sum of the fixed cost of locating new facility u at k and the cost of 
 
 satisfying the customer demand for new facility u from this location. If we denote C'ukvr = 
 
 b uv d(k,r) then our integer programming formulation of MMMC is: 
 
 (P) min I UG m!v(>u)€ M £re N^ke N C'ukvr XukXvr + Sue M^ke N FukXuk (6) 
 
 Subject to: (1), 
 
 x^ = {0,1} for all u,k. 
 
 The objective function of (P) consists of a quadratic term and a linear term in 
 variables x. The problem can be reformulated in which there is only a quadratic term in the 
 objective function. To do so, first we select a new facility u° for each new facility u such 
 that there is an interaction between new facilities u and u° (We are assuming, without loss 
 of generality, that the flow graph is connected). Then we define 
 Cukvr- Fuk + C'ukvr, V r if v=u°, and Cukvr=C'ukvr otherwise. (7) 
 
 With these costs, consider the following problem, which we call the Quadratic Location 
 Problem (QLP): 
 
 Min ZuSv>uSkSr CukvrXukXvr (8) 
 
 Subject to: (1), 
 
 x uk = {0,1} for all u,k. 
 We now show that problem (P) can be converted to a QLP. 
 
Lemma 1 : (P) can be formulated as a QLP. 
 
 Proof: (8) is same as:Z u Sv>u, v*u°XkXr Cukvr x uk x vr + Xu^kXr Cuku r x uk x u r 
 
 Using (7): = X u Xv>u, v*u°£k£r C'ukvr x ukXvr + ^u^k^r (C'uku°r + Fuk) x uk x u°r 
 
 =XuXv>u2-k2-r C'ukvr x uk x vr + XuXk £rF u k x uk x u°r 
 
 =2-u^v>u^k^-r C ukvr x uk x vr + 2-u^-k ^uk x uk **r x u°r 
 By (1): = I u Xv>uXkXr C , u kvr x uk x vr + XuXk Fuk x u k = (6). «» 
 
 Hence an MMMC can be reformulated as a QLP by redefining the costs as in (7). 
 Note that the QLP is a relaxation of the Quadratic Assignment Problem (QAP). In the QLP, 
 every facility has to be assigned to one site, but at any site multiple facilities (unlike QAP) 
 may be assigned. Thus, in the QAP there is an additional set of constraints, X u x uk =1. V 
 k, which is not in QLP. 
 
 Kolen has proven that MMMC is NP-hard. Since (as outlined above) MMMC can 
 be reformulated as a QLP, it follows that QLP is also NP-hard. We provide an alternate 
 proof of the complexity of the QLP by reducing a Simple Max Cut problem to QLP. We 
 note that the equivalence between quadratic 0-1 optimization and the (weighted) max cut 
 problem has been demonstrated in Barahona (1986). 
 
 Problem SIMPLE MAX CUT (SMC): Given a graph G with nodes V(G) and arcs E(G), 
 find a partition of V(G) into two disjoint sets Vi and V2 such that the number of arcs from 
 E(G) that have one endpoint in V] and one endpoint in V2 is maximum. 
 
 Theorem 1 : QLP is NP-hard. 
 
 Proof : As mentioned above, we establish this by showing that (SMC) can be reduced to 
 
 QLP. Given an (SMC) problem on a graph G, we construct a QLP by defining variables: 
 
 x u i=l if node u is in Vi, otherwise, for all ue V(G), and 
 
 x u 2 = 1 if node u is in V2, otherwise, for all ue V(G). 
 We also set Cukvr = 1 for k=r=l or 2, and arc (u,v) is in E(G); and Cukvr = otherwise. 
 Writing the QLP for this, we get: 
 
(QLP(G)) MinX^veMlk^S^uCukvrXukXvr (T 1 ) 
 
 Subject to: Xk=l,2 x u k =1, V u e V(G) (T2) 
 
 x u k={0,l}. <T3) 
 
 Given a graph G and a feasible solution {x^} to (QLP(G)) with value Zix^ we 
 can construct a feasible solution to (SMC) problem with value IE(G)I - Z(x ll j c ) as follows: 
 Form sets of nodes Vi={u : x u \ =1} and V2={u : x^ =1). Note that because {x^} 
 satisfies (T2), only one of x u \ or x^ will be equal to one and so VinV2=<t). Also, 
 V!UV 2 =V(G). 
 
 For a fixed u° and v°, the term C u o kv rXu k x v°r is equal to one if and only if k = r, 
 x u°k =1. x v ° r =1, and (u°,v°)e E(G). If C u °kv rXu°kXv o r =1 then by definition, both u° and v° 
 will be either in Vi or in V2. Thus the number of arcs of G with both endpoints either in Vi 
 or in V2 is Z(xuk). Hence the number of arcs with one node in Vi and other in V2 is IE(G)I 
 - Z(xuic). Minimizing (QLP(G)) is same as minimizing the number of arcs with their 
 endpoints in same sets Vi or V2, and hence same as maximizing the number of arcs which 
 have their endpoints in different sets, i.e. maximizing the cut. «» 
 
 In formulation (P) of MMMC, we have assumed that each new facility could be 
 located at any node of T. Suppose the location of a new facility u must be at a member of 
 some subset of the nodes of T, denoted by N u . In formulation (P), we could make use of 
 an artificial cost by setting the costs f^ for each node kg N u to be arbitrarily large. The 
 artificial costs would prohibit new facility u from being located at a node outside N u in an 
 optimal solution to MMMC. 
 
 In the next Section, we reformulate MMMC as a node selection problem, NSP. We 
 assume that N u is known for each new facility u, however, in our reformulation we will 
 not need to make use of the artificial fixed location costs mentioned above. 
 
8 
 3. Node Selection Problem 
 
 We now define a special graph, which we call a G-partite graph. We also define an 
 optimization problem, the node selection problem, on the G-partite graph. Subsequently, in 
 this Section, we show that the QLP can be posed as a node selection problem on a suitably 
 defined G-partite graph. 
 
 Definition: Given a graph G with an integer IN V I associated with each node v e V(G), a G- 
 Partite Graph, G° , is formed as follows: Corresponding to each node v e V(G) we create a 
 node-family , o~ v , in G° consisting of IN V I nodes {v^ : k = 1, ...,IN V I} (Figure 1). 
 Two nodes Uk and v r (v*u) are adjacent in G° if and only if arc (v,u) e E(G). Arc (uk,v r ) 
 in G° is assigned weight CO. . Thus if (v,u) exists in G, nodes of node-family o u and 
 node-family o v form a complete bi-partite subgraph of G°. Node-families G u and o~ v are 
 said to be adjacent if and only if every node in g u is adjacent with every node in o~ v . By 
 joining two node-families o~ u and o~ v we mean adding arcs between all pairs of nodes ' 
 ({ u k> v r) : tik £ o~u> v r e g v ). We will use the notation (o u ,c w ) to denote all arcs between 
 nodes in o~ u and nodes in o~ v . 
 
 A G-partite graph is a generalization of a complete bi-partite graph. A complete bi- 
 partite graph is a G-partite graph corresponding to a graph G which is a single arc. Given a 
 G-partite graph G°, let S(G°) be an induced subgraph of G° with one node of each node- 
 family and let Z(S(G )) be the sum of the weights on the arcs in S(G°) . We now pose the 
 following problem on G°: 
 
 (NSP) Node Selection Problem: Given a graph G and the corresponding G-partite graph, 
 G°, with arc weights co, find an induced subgraph consisting of exactly one node of each 
 node-family; such that the sum of all the arc weights on the arcs in the induced subgraph is 
 minimum. We will denote the node selection problem on G° by NSP(G°) and an optimal 
 solution by S*(G°). 
 
 Lemma 2 : Problem MMMC is reducible to NSP. 
 
 Proof: Given an MMMC problem with n existing facilities and m new facilities, we first 
 
formulate it as a QLP. Then we create a G-partite graph, G°, as follows. Create a node 
 family G u with IN U I nodes for every new facility u. Each of the IN U I nodes in a u 
 corresponds to a node of X where new facility u can be located. Join two node-families, 0" u 
 and o" v if and only if (u,v) e G. Recall that joining two node-families means forming a 
 complete bi-partite graph between nodes of o u and o* v . Assign the weight Cukvr, on the arc 
 (u k ,v r ) g E(G°) . 
 
 Given the G-partite graph constructed as above, we note that a feasible solution to 
 the NSP corresponds to a feasible solution to the QLP. Given a feasible solution S(G C ) to 
 the NSP, construct a feasible solution to QLP, X(S(G°)), as follows: set X(S(G°)) = {x u k 
 = 1 if node k of node-family o~ u is chosen, otherwise}. Since one node of each node- 
 family is in S(G°), constraint (1) is satisfied. Similarly if a feasible solution to the QLP is 
 given we can construct a feasible solution to NSP by choosing node u^ e o u if and only if 
 
 x u k= I. 
 
 A choice of nodes for department u and v contributes C^vr = ^Vj. t0 tne objective 
 function of QLP, which is the weight on arc (uk,v r ) in S(G°). Hence the value of S(G°) is 
 the same as the value of solution X(S(G )). Thus by solving appropriate NSP we will get a 
 solution to the QLP.«» 
 
 The above reduction shows that NSP is also NP-hard. Note that an NSP is more 
 general than QLP and many other problems can be modeled as an NSP (Section 7). 
 
 We have shown that, given an MMMC, it can be modeled as a QLP which in turn 
 can be reformulated as an NSP. Thus, an MMMC can be modeled as an NSP. The G- 
 partite graph for the MMMC will correspond to the flow graph G of MMMC. This is 
 because, if an arc (u,v) e E(G) then b uv =0 and so C u kvr = for all k,re N. And by (7) 
 C u kvr = for all k,re N. Thus node-families o u and G v will not be adjacent. 
 
 4. Polynomially Solvable Special Cases 
 
 In this Section we give a rich class of problems for which the node selection 
 problem is polynomially solvable. We have shown that we can use the node selection 
 
10 
 
 problem, NSP, to model MMMC. As we have shown, in general this problem is NP- 
 complete. The special cases we consider are characterized by the structure of the flow 
 graph, G. For the node selection problem, we are given G and the G-partite graph G°. We 
 associate, with each node and each arc of G° a label in the form of a set . Initially we set the 
 label of each arc e, L a (e) = { } , where { } denotes the empty set, and the label of each node 
 Uk, Ln(uk) = (uk) • We will represent the label of an arc e defined by two nodes p and q by 
 L a (p,q) rather than L a ((p,q)). 
 
 Later on, in the course of solving the Node Selection Problem for the special cases, 
 arcs and nodes of graphs G and G° will be deleted, in some cases (new) arcs will be added, 
 and labels of the remaining arcs, as well as the arc weights, will be modified to reflect the 
 change. The labels are used, basically, to carry pertinent information about the deleted 
 portion of the graph. In modifying the labels, we will typically add two labels, where 
 addition of labels is defined as the set union operation on the sets corresponding to the two 
 labels. In what follows, we assume that the flow graph is connected. If this is not the case, 
 e.g. the flow graph consists of more than one component, then MMMC can be solved by 
 solving (independently) an MMMC problem corresponding to each component. We begin 
 with some definitions and results from graph theory: 
 
 Definition : A graph is series-parallel (Richey, 1989) if it can be reduced to an arc by 
 repeated application of the following operations: 
 
 (Gl) Series Reduction: Replace any degree-2 node q, and the incident arcs (u,q) and (v,q), 
 u * v, by a new arc, a'(u,v), incident to u and v. 
 
 (G2) Cut Reduction: If q is a pendant node (a node of degree one) adjacent to node u, find 
 a node v * q adjacent to u, delete node q and add a new arc a'(u,v). . 
 (G3) Parallel Reduction: Replace two arcs e and f which are both incident to nodes u and v, 
 by a new arc, g, incident to u and v. 
 
 The new arcs that are added to the graph in the above operations are named pseudo- 
 arcs in (Richey, 1989). Richey describes an operation similar to operation (G2), calling it a 
 Jackknife reduction, but does not add the new arc a'(u,v). If we perform parallel reduction 
 on (u,v) immediately after the cut reduction, we get Richey's Jackknife reduction. Thus, 
 
11 
 
 although there is a minor difference in the definition of one operator, which we need for 
 our algorithm, the above definition of a series-parallel graph is identical to that of Richey. 
 
 To obtain insight into the structural nature of series-parallel graphs it is useful to 
 introduce the concept of a 2-tree. A 2-tree (Wald and Colbourn, 1983; Rardin, Parker, and 
 Richey, 1982) is defined recursively as follows: A triangle is a 2-tree. Given any arc (x,y) 
 of a 2-tree, by appending a node z and adding edges (x,y) and (y,z), the resulting graph is 
 also a 2-tree. The relationship between series-parallel graphs and 2-trees is that (Wald and 
 Colbourn, 1983) a series-parallel graph, without loops and parallel edges, is a subgraph of 
 some 2-tree. Thus, series-parallel graphs are sometimes called partial 2-trees. 
 
 Several authors have exploited the properties of series-parallel graphs. 
 Takamizawa, Nishizeki, and Saito (1982) have solved several combinatorial problems on 
 series-parallel graphs. Barahona (1986) has solved the 0-1 quadratic programming problem 
 when the graph representing the positive coefficients of the problem, i.e., the flow graph, 
 is series-parallel. Rendl (1986) solved a special case of the QAP by exploiting a series- 
 parallel digraph. Rardin, Parker, and Richey (1982) and Wald and Colbourn (1983) solved 
 the Steiner tree problem on a graph which is series-parallel, and Richey (1989) has solved 
 several location problems on transport networks which are series- parallel. 
 
 It is shown in Rardin, Parker, and Richey (1982) that series-parallel graphs 
 subsume circuits, outerplanar graphs, cactus graphs, and trees. Thus series-parallel graphs 
 generalize a number of graph types; however, they still form a subset of planar graphs. 
 
 We will soon define graph operations on a G-partite graph which are similar to the 
 operations (Gl), (G2), and (G3) discussed above. The outcome of two of these operations 
 will result in parallel arcs in the graph. We emphasize here that if there are parallel arcs 
 between two given nodes of a G-partite graph G°, and if this pair of nodes is in a feasible 
 solution S(G°) to NSP, then the parallel arcs are also in S(G°), so that the arc weights of 
 both arcs contribute to Z(S(G°)). 
 
 Let y be an arbitrary subset of nodes of a G-partite graph G° such that there is at 
 most one node of each node-family in \\f. Let NSP(G°,\|/) denote the co nstrained version of 
 NSP on G° with the set of nodes \\f fixed, and let S*(G°,\|/) denote an optimal solution to 
 NSP(G°,y) with objective function value Z(S*(G°,\|/)). Thus with { } denoting the empty 
 
12 
 
 set, S*(G°,{ }) is a solution to NSP(G°,{ }) = NSP(G°). 
 
 We now define three elementary operations on a G-partite graph, G°. These 
 operations are mirror images of similar operations performed on G so that the new G- 
 partite graph corresponds to G after the elementary operation. Although we give the same 
 name to these operations as in the case of G, the context will make it clear which procedure 
 we are referring to. We present these operations as procedures after describing the essence 
 of what they accomplish. These procedures will be repeatedly used by the main algorithm 
 SP which we will describe later. In Section 5 we give an example which uses each of these 
 procedures to solve the NSP using algorithm SP. The reader may refer to Section 5 while 
 going through these procedures to clarify the steps in each procedure. 
 
 (GP1): Series-Reduction : In this process a node-family o~ q such that node q is adjacent to 
 exactly two distinct nodes u and v of G, where q*v*u, is eliminated in G°. The reduced 
 graph has one less node-family. All the information pertinent to optimal node selection in a q 
 is retained, as is shown in the following process. For an example of this procedure see 
 Iteration 3 in Section 5. 
 
 PROCEDURE SR(CT q ) 
 
 Step 1 : Let u and v be the two nodes adjacent to node q in G, where q*u*v. 
 
 Step 2 For each pair of nodes Uk e o u , v r e o\, find q p ° giving 
 
 cojj?o + u/?o = min { co^ + co vq } (ties can be arbitrarily broken). 
 
 Add an arc a'(uk , v r ) with weight equal to 0)jJ? o + 0)!? o and 
 
 let the label of this new arc be L a '(v r ,uk) <— L a (v r ,q p °)uL a (uk,qp°)u L n (q p °) . 
 
 Step 3: Delete node-family c q . Return (to the calling algorithm). 
 
 Lemma 3 : For a G-Partite graph G° with a node-family o~q such that q has degree two in G, 
 let Q° and Q be the results of series-reducing node-family o~q and node q in G° and G, 
 respectively. Given an optimal solution S*(G°) to NSP(G°), an optimal solution to 
 NSP(G°) can be constructed using the nodes and arc labels of S*(£j°). Furthermore, the 
 complexity of procedure SR(.) is 0(IN u l*IN v l*INql) where u and v are the nodes of G 
 
13 
 
 adjacent to node q. 
 
 Proof: Let u and v be the two nodes adjacent to node q in G and let A' denote the set of arcs 
 added to G° in procedure SR(.). For any choice u k . e o u and v r ^ e o v , we note that with 
 \}/={u k ° v r °}, a) S*(G°\A\\j/), which is an optimal solution to NSP(G°\A',\j/), is also an 
 optimal solution to NSP(G°\A',\j/), and b) S*(G°\A',\|/) has the same objective function 
 value when evaluated in graphs G°\aq and G°\A'. Observations a) and b) follow since the 
 graphs G°\rjq and G°\A' are the same. 
 
 Considering NSP(G°), we note that for fixed u k . e a u and v r ° e a v , the choice of 
 an optimal node in Oq is independent of the optimal choices in the graph G°\{a u UG v UGq}. 
 Thus, one way to solve NSP(G°) is to find 
 
 In graph G°, for u k e c u , v r e G v , the arc a'(u k ,v r ) carries the essential information (labels 
 
 min {Z(S*(G°\G q ,{u k v r })) + min { co£ + oTM } 
 
 u k eC u 'v r eo v q ' 1 K ' qpeo q kp rp 
 
 and value) of the inner minimization problem above. Letting w(a'(uk,v r )) denote the weight 
 on arc a'(uk,v r ) in G°, we note that NSP(G°) can be solved by solving 
 
 min (Z(S*(G°\a q ,{u k v r })) + w(a'(u k ,v r ))}. 
 
 The first part of the Lemma now follows. 
 
 The complexity of finding node q p ° in Step 2 of SR(.) is O(INql). This Step is 
 repeated IN U I*IN V I times, hence the complexity of the procedure is 0(IN u l*IN v l*IN q l). «» 
 
 (GP2) Cut Reduction: Given two node-families a q and a u such that node q is a pendant 
 node in G, (q,u) e E(G), and (q,u) is not the only arc of G, we delete node-family a q and 
 add parallel arcs to the G-partite graph. The procedure which follows sketches the steps. 
 The example in Section 5 uses CR(.) during Iteration 1. 
 
 PROCEDURE CR(a q , o u ) 
 
 Step I: With q a pendant node of G adjacent to u, select an arc (u,v) of G, v*q. (Such 
 an arc exists because we have assumed that (u,q) is not the only arc of G and 
 throughout we assume that G is connected.) 
 Step 2: For each node u k of a u , 
 
 Find a node q p ° of node-family a q such that co^o = min g { w k p) (ties 
 
14 
 
 can be arbitrarily broken). 
 
 In G° add new arcs a'(uk , v r ) for all v r e g v with weight co^ and 
 
 set the label of these new arcs L a '(uk , v r ) <— Ln(q p °) uL a (qp°,uk). 
 
 Step 3: Delete all the nodes of node-family c v in G°, i.e. delete o v . 
 
 Step 4: Return. 
 
 Lemma 4: For a G-Partite graph G° with a node-families o~ u and o~q such that (u, q) e E(G), 
 node q is a pendant node in G, and u and q are not the only nodes of G, let G° and G be the 
 results of cut-reducing node-families o u and Oq in G° and nodes u and q in G. Given an 
 optimal solution S*(G°) to NSP(£}°), an optimal solution to NSP(G°) can be constructed 
 using nodes and arc labels of S*(G°). Also, reducing G° to G° can be done in 
 0(IN u l*(IN v l+INql)) time where v is the node selected in Step 1. 
 
 Proof: Let A' denote the set of new arcs added between nodes in a u and ov Consider an 
 arbitrary node uk° e a u in G°. Since graphs G°\a q and GAA' are the same with \|/={uk°}, it 
 follows that S*(G°\A\\}0, an optimal solution to NSP(G°\A',\}/), is also an optimal solution 
 to NSP(G°\Oq,y) and S*(Q°\A\\|/) has the same objective function value when evaluated in 
 graphs G°Vj q and G°\A\ 
 
 Also, due to the structure of G°, a way of solving NSP(G°) is to find 
 min u k ea u (Z(S*(G°\a q ,{u k })) + min qp6 {co^} }. In graph Q° with u k eo u fixed, 
 there is an added arc a'(uic,v r ) for every v r e o v and each such arc carries the essential 
 information (labels and value) of the inner minimization problem above. Since any feasible 
 solution to NSP(G°) and any feasible solution to NSP(£j°) must contain one node of G v , the 
 first part of the Lemma follows. 
 
 In Step 2 of CR(.), node q p ° can be found in O(INql) time and arcs a'(uk°,v r ) V 
 VfG o" v , can be updated in 0(IN v l) time. This process is repeated for each node in o~ u , i.e. 
 IN U I times. Thus the total complexity of this Step is 0(IN u l*(IN v l + INql)). «» 
 
 (GP3) Parallel Reduction: Initially in G there are no parallel arcs. However, as the main 
 algorithm SP (described later) proceeds, parallel arcs may be created in G and G°. In 
 particular, parallel arcs in G (G°) may be created during series-reduction of node q (a q ) 
 with adjacent nodes u and v (a u and a v ). Series-reduction would add an arc between u and 
 
15 
 
 v in G (add arcs (o~ u , o v ) between o u and o~ v in G°) and if u and v (o u and o\) were 
 adjacent before the series-reduction then there would be parallel arcs between nodes u and v 
 (o u and a v ) after the series-reduction. Parallel arcs are always created during cut-reduction. 
 For an illustration of this procedure, see Iteration 2 of the example in the next Section. 
 
 Given two node-families o u and o v such that there are two arcs between every node 
 Uk e o~ u and v r e o* v , w e replace the parallel arcs by a single arc. The weights and the 
 labels associated with the two parallel arcs are added and they form the weight and label, 
 respectively of the new arc. Procedure PR(.) describes this process. 
 
 PROCEDURE PR(a u , c v ) 
 
 Step 1: Let nodes uk e 0" u and v r e a v be such that there are two arcs between them. 
 Delete one of these arcs and add its weight to the weight of the other arc. Also 
 add the label of this deleted arc to the label of the second arc. 
 
 Step 2: Continue Step 1 until no parallel arcs between nodes of o u and o~ v remain. 
 
 Step 3: Return. 
 
 Lemma 5: For a G-Partite graph G° with node-families o~ u and o~ v such that there are two 
 arcs between every node uk e o~ u and v r e a v , let Q° and Q be the results of parallel- 
 reducing node-families o~ u and o v of G° and nodes u and v in G. Given an optimal solution 
 S*(Q°) to NSP(£j°), an optimal solution to NSP(G°) can be constructed using the nodes 
 and arc labels of S*(G°). Furthermore, PR(.) can be performed in 0(IN u l*IN v l) time. 
 Proof: The first part of the Lemma easily follows from the fact that for each Uk° e o~ u and 
 v r ° e o~ v , the weight and label on arc (uk°,v r °) e G° is equal to the sum of the weights and 
 the union of the labels on the parallel arcs (uk°,v r °) e G°, and the fact that graphs 
 G°\(a u ,Ov) and G°\(o u ,Ov) are the same. 
 
 Since there are IN U I nodes in o u and IN V I nodes in a v , there will be IN U I*IN V I 
 repetitions of Step 1. Each repetition of Step 1 takes constant time and so the complexity of 
 the procedure is as stated. «» 
 
 We now present an algorithm which correctly solves NSP in polynomial time when 
 
16 
 
 the flow graph G is series-parallel. Without loss of generality we assume that G is 
 connected. In the algorithm, during Iteration 1, graphs G and G° are denoted as Gi and 
 G°i, respectively. During each iteration these graphs will be changed and at a general 
 Iteration k, these graphs will be denoted by Gk and G°k. Algorithm SP proceeds by 
 forming a set, denoted as 2D, of degree two nodes in Gi. PA is the set of node pairs 
 having parallel arcs in the current Gk. Initially PA is empty. First we cut-reduce the pendant 
 nodes in Gk and G°k followed by parallel-reduction of the parallel arcs formed during the 
 cut-reduction. Then a series-reduction is performed (if 2D * { }) followed by a parallel- 
 reduction, if parallel arcs are formed due to the series-reduction. If these reductions create a 
 new pendant node, that node is eliminated by cut-reduction and the process is continued 
 until a single arc is left in Gk. The best arc in G°k at this stage is chosen, the weight of 
 which gives the solution value. The solution to NSP in G° is generated by the end nodes of 
 this arc and the nodes contained in the label of this arc (Step 6). 
 
 ALGORITHM SP 
 
 Step 0: Set k<- 1, G°k <- G°, Gk <- G. 
 
 Let 2D denote the list of nodes in Gk with degree 2. PA is the list of node pairs 
 
 having parallel arcs in Gk- For our problem, initially PA will be empty as there 
 
 are no parallel arcs in the flow graph G. 
 Step 1 : If Gk is a single arc then go to Step 6 else find a node q e V(Gk) with degree 
 
 one and go to Step 2. If there exists no such node then go to Step 3. 
 Step 2: Let (q,u) e E(Gk) be the arc connecting q to another node u. 
 
 Cut Reduce node-families a u and a q in G°k by calling procedure CR(a q ,o~ u ). 
 
 Cut Reduce nodes u and q in Gk- 
 
 Let node v be such that it is adjacent to u in Gk and is used in CR(.). Add (u,v) 
 
 to PA. 
 
 Set Gk+i <r- Gk (after cut-reduction) 
 
 G°k + i <— G\ (after cut-reduction) 
 k<-k+l. 
 
 Go to Step 5. 
 
17 
 
 Step 3: If I2DI = then go to Step 5; else choose a node qe 2D. Let nodes u and v be 
 
 adjacent to q in Gk- 
 
 Step 4: If (u, v) e E(G k ) then add (u, v) to PA. 
 
 Series-reduce node-family o~ q by calling procedure SR(Oq). 
 
 Series-reduce node q. 
 
 Set Gk + i <— Gk (after series-reduction) 
 
 G°k+i <r- G°k (after series-reduction) 
 
 k<-k+l 
 
 Delete q from 2D and go to Step 5. 
 
 Step 5: If IPAI = then go to Step 1; else let (u, v) e PA. 
 
 Parallel-reduce arcs between node-families o u and a v by calling procedure 
 
 PR(a u ,a v ). 
 
 Parallel-reduce arcs between nodes u and v 
 
 Set Gk-t-i <— Gk (after parallel-reduction) 
 
 G°k + i <— G\ (after parallel-reduction) 
 
 k<-k+l 
 
 If u (or v) has degree 2 in Gk, add it to 2D. 
 
 Go to Step 1. 
 
 Step 6: At this stage G is a single arc (u, v). Find 
 
 go, o o = min, { co " v } . This is the value of the optimal solution and 
 
 * r ke (j u re a v kr J 
 
 the solution can be constructed by L a (uksv r °)uL n (uk°)uL n (v r °). Stop. 
 
 Theorem 2: Algorithm SP correctly solves NSP in polynomial time when the flow graph G 
 is series-parallel. 
 
 Proof : Algorithm SP first cut-reduces all of the pendant nodes of G with each cut- 
 reduction followed by a parallel-reduction. It then performs a series-reduction and a 
 parallel-reduction, if needed. This is followed by a cut-reduction if necessary. This 
 process, if repeated, must reduce G to a single arc if G is series-parallel. The graph 
 obtained after each reduction remains series-parallel. We also perform the corresponding 
 operations on G°. Each of these reductions, by Lemmas 3, 4, and 5, preserves the solution 
 to NSP on the original graph G°. Finally, when only a single arc is left in G, the node 
 
18 
 
 selection problem can be trivially solved as in Step 6 of SP. The end nodes of the single arc 
 selected in Step 6 provide the two nodes to be selected from the node-families that remain 
 in Step 6. The nodes to be selected from other node-families, which were in the original 
 graph G°, are given by the labels on the arc selected in Step 6. 
 
 To show the polynomial complexity we note that every cut-reduction and every 
 series-reduction eliminates one node of the flow graph. Furthermore, each such reduction 
 adds at most one parallel arc to the flow graph. If G has (3 nodes, there cannot be more than 
 (3 series and cut-reductions and at most (3 parallel-reductions. Since the complexity of 
 series-reduction dominates the complexity of other two reductions, the complexity of 
 algorithm SP is bounded above by the effort for P series-reductions. If X = maximum 
 {IN u I:ug V(G)}, then this bound is given by 0(p*X 3 ).«» 
 
 Corollary : The complexity of solving an MMMC problem with m new facilities and n 
 nodes when the flow graph is series-parallel is 0(m*n 3 ). «» 
 
 5. An Example of NSP When the Flow Graph is Series-Parallel 
 
 Consider the flow graph G and the G-partite graph, G° in Figure 1. Figure 2 shows 
 the weights on the arcs in G° which are presented in the form of matrices. The problem data 
 in Figures 1 and 2 were possibly derived from an instance of MMMC by using equations 
 (2) through (7). We do not illustrate the reduction of MMMC to NSP as doing this is fairly 
 straightforward. Note that in this problem, new facilities a and c are each restricted to one 
 of two locations, and new facilities b and d each have three potential location sites. The 
 entry in row 1 and column 3 of the first of the matrices in Figure 2 is the weight of the arc 
 joining node 1 of o c and node 3 of Gd- In G°, the label on the arc joining nodes Uk and v r is 
 L a (uk,v r )= { } and the label on each node Uk is L n (uk)={uk}. Now we apply algorithm SP 
 to solve NSP on G°. 
 Iteration 1 : 
 Step 0: k <-l, G°if-G°, Gi<-G. 
 
 2D={a,b}. 
 
19 
 
 Step 1: Vertex d in Gi has degree one. Go to Step 2. 
 
 Step 2: d is adjacent to c and (d,c) is not the only arc of Gi. Call procedure CR(Gd,0" c ). 
 Procedure CRfa^oV) 
 
 Step 1: Select arc (c,a) of Gi 
 Step 2: For node ci of G c 
 
 min of {5,4,8} is 4 and occurs for node d2 
 
 In G°i add arcs a'(ci,ai) and a'(ci,a2), each with cost 4 and 
 label {d 2 }. 
 For node c 2 of a c , 
 min of {7,9,6} is 6 and occurs for node d3 in o~d- 
 
 In G°i add arcs a'(c2,ai) and a'(c2,a2), each with cost 6 and 
 label {d 3 }. 
 . Step 3: Delete o c 
 Step 4: Return 
 Set this graph to G°2 
 
 Cut reduce node d in Gi and set this graph to G2 (Figure 3 ). 
 Set k to 2 
 
 {In Figure 3b, the first matrix corresponds to the weights on the new arcs that are 
 added in Iteration 1 } 
 Add (c,a) to PA and go to Step 5. 
 Iteration 2: 
 
 Step 5: We choose (c,a) e PA and call procedure PR(a c ,a a ). 
 Procedure PRCGp.qQ 
 
 Step 1: Pick nodes ai e o~ a , c\ e a c 
 
 m 
 
 Delete one of the two parallel arcs. Add the weight and label of the 
 deleted arc to the weight and label of the other arc (new weight = 
 5+4 = 9; new label = { }u{d 2 } = {d 2 }). 
 Step 2: We continue Step 1 until no parallel arcs remain between o c and o~ a . 
 Step 3: Return. 
 Parallel reduce arcs between nodes a and c in G2. 
 Update G3, G°3. Set k to 3. Since c has degree 2 add c to 2D and go to Step 1 (see 
 
20 
 
 Figure 4). 
 Iteration 3 : 
 
 Step 1: Since we do not have a pendant node, we go to Step 3. 
 Step 3: We choose node c e 2D with b and a the adjacent nodes to c in G3. 
 Step 4: Since (b,a) is in G3, we add (b,a) to PA . 
 Call procedure SR(a c ). 
 Procedure SR(oV ) 
 
 Step 1: b and a are two nodes adjacent to node c in G2 
 Step 2: Consider nodes b\e o~b and aie o a 
 
 t^' 1 • /* r DC 3C DC ciC 
 
 Find min of (co,, + co,,, co 12 + co 12 
 orminof {9+9, 19+13} = 18 
 Minimum occurs for node cie G c 
 Add arc a'(bi,ai) with weight 18 
 Set the label L a '(bi,ai) f- L a (bi,ci)uL a (ai,ci)u L n (ci) 
 orL a «(bi,ai)={}u{d2}u{ci}={ci,d2} 
 Consider nodes b\e 0"b and a2e o a 
 
 t"'* 1 • r ( DC 3C DC HC 
 
 Find min of {co,, + co 21 , co 12 + co 22 
 or min of {9+11,19+16} = 20 for node ci 
 Add arc a'(bi,a2) with weight 20 
 Set the label L a -(bi,a2) <~ L a (bi,ci)uL a (a2,ci)u L n (ci) 
 orL a '(bi,a 2 )={}u{d2}u{ci}={ci,d 2 } 
 
 Consider nodes D2eo"b and aiea a 
 
 Find min of {co 21 + co,,, co 22 + co, 2 
 
 or min of { 1 1+9,6+13} = 19 for node C2 
 
 Add arc a'(D2,ai) with weight 19 
 
 Set the label L a '(b2,ai) <- L a (b2,C2)uL a (ai,C2)u L n (c2) 
 
 orL a '(b 2 ,ai)={}u{d3}u{c2}={c2,d 3 } 
 
 Consider nodes b2e o~b and a2e a a 
 
 Find min of {co 21 + co 21 , co 22 + co 22 
 
 or min of { 11 + 11,6+16} = 22 for node C2 
 
 Add arc a'(D2,a2) with weight 22 
 
21 
 
 Set the label L a '(b2,a2) <- L a (b2,C2)uL a (a2,C2)u L n (c2) 
 or L a '(b2,a2)={ }u{d3}u{c2}={c 2 ,d 3 } 
 Consider nodes b3GGb and aiea a 
 
 t^* i • f* € DC 3C DO <-lC 
 
 Find min of {co^, + co,,, co 32 + &> 12 
 or min of {14+9,12+13} =23 for node ci 
 Add arc a'(b3,ai) with weight 23 
 Set the label L a '(b3,ai) <— L a (b3,ci)uL a (ai,ci)u L n (ci) 
 or L a «(b3,ai)={ }u{d2>u{ci }={ci,d 2 } 
 Consider nodes b^e Gb and a2£ 0" a 
 
 Find min of {co 31 + co, 2 , co 32 + w 22 
 
 or min of {14+11,12+16} = 25 for node ci 
 
 Add arc (b3,a2) with weight 25 
 
 Set the label L a '(b3,a2) «- L a (b3,ci)uL a (a2,ci)u L n (ci) 
 
 orL a '(b3,a2)={}u{d 2 }u{ci}={ci,d2} 
 Step 3: Delete a c . Return. {See Figure 5 for the weights and labels on 
 parallel arcs between a a and Cb- 
 Series reduce c in G3. 
 
 Update G3 and G°3, set k to 4 and go to Step 5. 
 Iteration 4: 
 
 Step 5: Edge (b,a)e PA. Call PR(a b ,a a ). 
 Procedure PR(a h.oy) 
 
 Step 1 : Choose nodes aje a a and b\e Ob, 
 
 Delete one of the two parallel arcs. 
 Add the weight of the deleted arc to the other arc 
 giving the weight as 18+7=25. 
 Add the labels on the two parallel arcs 
 = {cid 2 }u{}={cid 2 } 
 Step 2: We continue Step 1 until no parallel arcs remain (Figure 6 
 
 give the weights and labels, before and after this reduction). 
 Step 3: Return. 
 Parallel reduce arcs between nodes b and c in G4. 
 
22 
 
 Update G4, G°4. 
 
 Set k to 5 and go to Step 1. 
 Iteration 5: 
 
 Step 1: G4 is a single arc, so we go to Step 6. 
 Step 6: We find cofo, = min k6 ab fG ^ {© £} . 
 
 = min {25,24,23,27,31,29} = 23 and occurs for a r °=ai and bk°=b2 
 
 This is the value of the optimal solution. 
 
 The solution can be constructed by L a (b2,ai)uL n (b2)uL n (ai)={c2,d3,b2,ai} 
 
 Thus choose node C2^ a c ,d3G o~d,b2e 0"b, and aie o~ a . Stop. {The dark edges along 
 
 with the nodes incident by the dark edges in Figure 7 depicts the solution. } 
 
 6. M-Center Problem With Mutual Communication 
 
 In the m-center problem with mutual communication (as defined by Kolen (1982)), 
 we want to find the location of the m new facilities to minimize the maximum of the 
 interaction costs of new and existing facilities, interaction costs of pairs of new facilities, 
 and the fixed cost of locating a new facility (this term is not included in (Kolen, 1982)). In 
 what follows, we consider the node-restricted version of the problem. There is no loss of 
 generality here since we can find (see Hooker, Garfinkel, and Chen , 1988) a finite number 
 of points on the transport network such that in an optimal solution to the problem each new 
 facility will be at one of the points. Thus we can declare these points to be nodes of X. In 
 our version of the problem, denoted by MCMC, we assume each existing facility is located 
 at some node of X. Thus we again use the convention that nodes of X (as well as locations 
 of existing facilities) are indexed by k, r, and i. Similar to (MMMC), if there is a node of X 
 with no existing facility, we simply declare it to be an existing facility which has zero 
 interaction with all existing facilities. In addition, we will consider the fixed location costs 
 of the new facilities. 
 
 We now describe a G-partite graph G° and a bottleneck version of NSP, denoted by 
 B-NSP, on G°, which if solved, will solve (MCMC). For each new facility, u, we again 
 
23 
 
 define a node-family g u , consisting of nodes {uk, ke N u } where N u is the set of feasible 
 locations (nodes of T) for new facility u. If new facility u interacts with new facility v, i.e., 
 b uv > 0, there is an arc in G° between every member of a u and c v . Consider uk e o u and v r 
 e o v . A choice of these nodes corresponds to new facility u being located at node k of X 
 and new facility v being located at node r of X. The cost of arc (uk,v r ) is defined to be 
 maximum of the following terms: a) f u k, b) f vr , c) b uv d(k,r), d) max; (a v id(r,i)}, and e) 
 max; {auid(k,i)}. Terms a) and b) reflect the fixed cost of locating new facilities u and v at 
 nodes k and r, respectively. Term c) is the cost of interaction between new facilities u and 
 v, given their locations. Term d) (e)) represents the maximum cost of interaction between 
 new facility v (u) and any existing facility. 
 
 With this definition of the cost of each arc in G°, the B-NSP on G° to solve 
 (MCMC) can be stated as follows: find an induced subgraph, S(G°), of m nodes of G°, 
 such that S(G°) contains one node of each node-family and where the maximum of the arc 
 costs of the arcs of S(G°) is minimum. 
 
 We now point out the changes required in the procedures described in Section 4 to 
 solve B-NSP. Algorithm SP remains identical except that instead of calling procedures CR, 
 PR, and SR, it will call procedures CR (as before) as well as SR' and PR', described 
 below. To distinguish these procedures from the previous procedures we name them b- 
 series-reduction and b-parallel-reduction, respectively. 
 
 PROCEDURE SR'(o q ) 
 
 Step 2 For each pair of nodes Uk e o u , v r e a v , find q p ° giving 
 
 max{to£> , CO^o) = min^ {max{co u k q p , co^} }. 
 
 Add an arc a'(uk , v r ) with weight equal to max{co? q , <^3) and 
 
 Kp rp 
 
 let the label of this new arc be L a '(v r ,uk) «- L a (v r ,q p °)uL a (uk,qp )u L n (q p °) . 
 
 Lemma 3' : For a G-Partite graph G° with a node-family o~q such that q has degree two in G, 
 let G° and G be the results of b-series-reducing node-family o~q and node q in G° and G, 
 respectively. An optimal solution to (B-NSP) on G° can be constructed using the nodes and 
 arc labels of an optimal solution to (B-NSP) on G°. Furthermore, the complexity of 
 
24 
 
 procedure SR'(.) is 0(IN u l*IN v l*INql) where u and v are the nodes of G adjacent to node q. 
 Proof: In the objective function of NSP the sum of arc weights is computed whereas in B- 
 NSP, the maximum of arc weights is taken. Thus, while performing the b-series-reduction, 
 instead of looking at the sum of weights on arcs (uk,q p ) and (v r , q p ) we focus on the 
 maximum of the weights on these two arcs. The proof follows exactly the same arguments 
 as in the proof of Lemma 3, except that the '+' operator is replaced by the 'max' operator. 
 «» 
 PROCEDURE PR'(a u , G v ) 
 
 Step 1 : For any two nodes u^ e a u and v r e o~ v such that there are parallel arcs between 
 them, replace the parallel arcs by a new arc with weight equal to the maximum 
 of arc weights on the arcs just deleted and label equal to the union of the labels 
 on the deleted arcs. 
 Lemma 5': For a G-Partite graph G° with node-families a u and o" v such that there are two 
 arcs between every node u^ e o~ u and v r e a v , let G° and G be the results of b-parallel- 
 reducing node-families 0" u and o~ v of G° and nodes u and v in G, then an optimal solution 
 to (B-NSP) on G° can be constructed using the nodes and arc labels of an optimal solution 
 to (B-NSP) on G°. Furthermore, PR'(.) can be performed in 0(IN u l*IN v l) time. 
 Proof: The proof of this Lemma is similar to the proof of Lemma 5, but again the 'max' 
 operator is replaces the '+' operator. «» 
 
 Note that no modifications are required in PROCEDURE CR(.). Following the 
 notation as in CR, for any node Uk e a u , the node in 0"q for B-NSP will also be selected by 
 finding q p ° which minimizes oar*. If we add additional arcs A' , and delete Gq, the solutions 
 on the two graphs for B-NSP remain equivalent (see proof of Lemma 4). 
 
25 
 7. Conclusions 
 
 In this paper we have provided polynomial time algorithms for special cases of the 
 m-median and m-center problems with mutual communication. The special case is 
 characterized by the structure of the flow graph. First, we reformulated the m-median 
 problem with mutual communication as a quadratic location problem which was then 
 formulated as a node selection problem posed on a G-partite graph. Then we presented an 
 algorithm (Algorithm SP) which solves NSP when the flow graph is series-parallel. The 
 m-center problem with mutual communication was formulated as the bottleneck version of 
 the node selection problem (B-NSP). We presented the modifications required in Algorithm 
 SP to solve B-NSP. 
 
 Algorithm SP is a general algorithm to solve any problem which can be modeled as 
 an NSP. As an example, consider the 0-1 quadratic programming problem (Barahona, 
 1986): 
 
 (QP): min l/2xtQx + ex = Zi=i.. n Ej=i+i... n QijXiXj + Zi=i.. n CiXi, x e {1,0}. 
 To model QP as an NSP we create a G-partite graph, G°, with a node-family for each x { 
 which has two nodes, n;o and nn. Node nio (n\\) corresponds to the variable x\ taking the 
 value (1). Join two node-families if and only if qy > 0. The weight on arc (nn, riji) is 
 initially set equal to q,j and all other arcs between C[ and Oj are initially given weight 0. To 
 account for the linear costs Cj, we select a j such that qij > 0, and add c\ to the weight on 
 arcs (nn, n j0) ar >d ( n ii» n jl)- It is easy to see that NSP(G°) is a reformulation of QP. Thus 
 when the graph defined by qjj's is series-parallel, QP can be solved in 0(n*2 3 ) time. As we 
 noted earlier, Barahona (1986) also has a linear time algorithm for this case of QP but he 
 solves it by converting it to a weighted max-cut problem on a graph H which has one 
 additional node adjacent to all nodes of the flow graph defined by the qy's. 
 
 We now discuss certain generalization of series-parallel flow graphs for which NSP 
 can be solved in polynomial time. To give an example of this generalization, consider a 
 series-parallel graph G' and a graph Bi which has two special nodes, u' and v\ denoted as 
 terminals (Figure 8). If we replace arc (u,v) in G by the graph Bi we get a graph G which 
 is no longer series-parallel (Figure 9). Here we define replacement of an arc (u,v) of a 
 
26 
 
 graph G' by a graph Bi (with two terminals u' and v') as: delete arc (u,v) in G' and attach 
 graph Bi to G' such that node u' coincides with node u and node v' coincides with node v. 
 
 In order to solve an NSP on a G-partite graph, G°, corresponding to the flow graph 
 G defined above, we proceed as follows: for a choice of node pairs Uk° e a u and v r ° e a v , 
 find the optimal nodes in node-families o n i and o*n2 ^d let these two nodes be denoted by 
 the set R(k°,r°). Note that once we choose nodes Uk° e G u and v r ° e cr v , the optimal choice 
 of nodes in o~ n i and a n 2 is independent of the solution on the remainder of G. Also, note 
 that due to the structure of Bi, finding the optimal nodes on the remainder of B\, i.e., 
 finding R(k°,r°), with uk° and Vr° fixed can be done in polynomial time. Let w(k°,r°) denote 
 the sum of the weights on the arcs in the graph induced by nodes {uk o ,v r °}uR(k ,r )- Insert 
 arc (uic°,v r o ) with weight w(k°,r°) in G°. Repeat this process for every choice of node pairs 
 Uk e o~ u and v r e a v , then delete node families 0" n i and a n 2 from the G-partite graph G°. 
 The new G-partite graph corresponds to the series -parallel flow graph G'. It is easy to see 
 that given an optimal solution to NSP on the new G-partite graph we can construct an 
 optimal solution to NSP on the original G-partite graph. Thus, we can solve NSP with 
 flow graph G in Figure 9, which is not series-parallel, in polynomial time 
 
 To generalize the above, we define a family of graphs, it. Graph Bj is a member of 
 K if there are two terminal u and v of Bj, such that for arbitrary fixed nodes, Uk° e 0" u and 
 Vr° e o v , S*(G°(Bi), \\f) can be computed in polynomial time, where G°(Bi) is the G-partite 
 graph corresponding to Bj and with \\f = {u^, v r °). If we obtain a flow graph G by 
 replacing some arcs of a series-parallel graph by a member of k, we can still solve NSP 
 with flow graph G in polynomial time. Campbell and Rardin (1987) have defined a similar 
 class of generalized series-parallel graphs, which they called series- parallel block graphs, 
 and they give an algorithm to recognize the series-parallel block graphs in polynomial time. 
 The algorithm in (Campbell and Rardin, 1987) when applied to a graph G, will give a set 
 of graphs with two terminals. If all the graphs in this set are member of the family n, then 
 NSP on G can be solved in polynomial time. 
 
27 
 
 References 
 
 Barahona, F., "A Solvable Case of Quadratic 0-1 Programming," EH sere te Applied 
 Mathematics , Vol. 13, 1986, pp. 23-26. 
 
 Campbell, B. A. and R. L. Rardin, "Steiner Tree Problem on Series-Parallel Block Graphs 
 I: Polynomial Recognition and Solution," Tech. Report CC-87-17, School of Industrial 
 Engineering, Purdue University. 
 
 Dealing, P. M, R. L. Francis, and T. J. Lowe, "Convex Location Problems on Tree 
 Networks," Operations Research . Vol. 24, 1976, pp. 628-642. 
 
 Erkut, E., R. L. Francis, and T. J. Lowe, "A Multimedian Problem with Interdistance 
 Constraints." Environment and Planning B: Planning and Design . Vol. 15, 1988, pp. 181- 
 190. 
 
 Erkut, E., R. L. Francis, T. J. Lowe, and A. Tamir, "Equivalent Mathematical 
 Programming Formulations of Monotonic Tree Network Location Problems," Operations 
 Research . Vol. 37(3), 1989, pp. 447-461. 
 
 Francis, R. L., T. J. Lowe, and H. D. Ratliff, "Distance Constraints for Tree Network 
 Multifacility Location Problems." Operations Research . Vol. 26, 1978, pp. 570-596. 
 
 Hooker, J. N., R. S. Garfinkel, and C. K. Chen, "Finite Dominating Sets for Network 
 Location Problem," Working Paper 19-87-88, Carnegie Mellon University, March 1988 
 
 Kolen, A., "Location Problems on Trees and in the Rectilinear Plane," Stitch ting 
 Mathematisch centrum, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands, 1982. 
 
 Picard, J-C and H. D. Ratliff, "A Cut Approach to the Rectilinear Distance Facility 
 Location Problem," Operations Research . Vol. 28, 1978, pp. 422-433. 
 
 Rardin, R. L., R. G. Parker, and M. B. Richey, "A Polynomial Algorithm for a Class of 
 Steiner Tree Problems on Graphs," ISyE Report Series J-82-5, Georgia Tech., August, 
 1982. 
 
 Rendl, F., "Quadratic Assignment Problems on Series-Parallel Digraphs," Zeitschrift fur 
 Operations Research . Vol. 30, 1986, pp. A161-A173. 
 
 Richey, M. B., "Optimal Location of a Path or Tree on a Network with Cycles," Working 
 Paper, George Mason University, 1989. 
 
 Takamizawa, K., T. Nishizeki, an S. Saito, "Linear- Time Computability of Combinatorial 
 Problems on Series-Parallel Graphs," J. of the ACM . Vol. 29, 1982, pp. 623-641. 
 
 Wald, J. A. and C. J. Colbourn, "Steiner Trees, Partial 2-Trees, and Minimum DFI 
 Networks." Networks . Vol. 13, 1983, pp. 159-167. 
 
 Xu, Y., R. L. Francis, and T. J. Lowe, "The Multimedian Problem on a Network: 
 Exploiting Block Structure," Working Paper, Department of Industrial and Systems 
 Engineering, University of Florida, Gainesville, Florida, 1988. 
 
28 
 
 Graph G 
 (a) 
 
 IN a l = IN C I = 2, IN b l = IN d l =3 
 G-Partite Graph G° 
 (b) 
 
 Figure 1 . Graphs G and G ( 
 
 Weights 
 
 
 
 X 
 
 1 
 
 2 
 
 3 
 
 1 
 
 5 
 
 4 
 
 8 
 
 2 
 
 7 
 
 9 
 
 6 
 
 Weights 
 
 
 * 
 
 1 
 
 2 
 
 1 
 
 5 
 
 7 
 
 2 
 
 7 
 
 10 
 
 Weights 
 
 
 
 ^ 
 
 1 
 
 2 
 
 3 
 
 1 
 
 9 
 
 11 
 
 14 
 
 2 
 
 19 
 
 6 
 
 12 
 
 Weights 
 
 s 
 
 1 
 
 2 
 
 3 
 
 1 
 
 7 
 
 4 
 
 8 
 
 2 
 
 4 
 
 5 
 
 4 
 
 Figure 2. Weights on G° 
 
29 
 
 New arcs 
 
 (a) Graph G2 
 
 Weights 
 
 Weights 
 
 
 ^ 
 
 1 
 
 2 
 
 * 
 
 1 
 
 2 
 
 1 
 
 4 
 
 4 
 
 1 
 
 5 
 
 7 
 
 2 
 
 6 
 
 6 
 
 2 
 
 7 
 
 10 
 
 Weights 
 
 
 
 > 
 
 1 
 
 2 
 
 3 
 
 1 
 
 9 
 
 11 
 
 14 
 
 2 
 
 19 
 
 6 
 
 12 
 
 (b) Weights on arcs in G°2 
 
 Weights 
 
 s 
 
 1 
 
 2 
 
 3 
 
 1 
 
 7 
 
 4 
 
 8 
 
 2 
 
 4 
 
 5 
 
 4 
 
 La*(ci,ai)= {d2} 
 L a '(c2,ai)= {d3} 
 
 L a '(ci,a2)= {d2} 
 L a '(c2,a2)= {d3} 
 
 (c) New Labels 
 Figure 3. End of iteration 1 
 
 (a) Graph G3 
 
 Weights 
 
 
 Weights 
 
 
 
 V 
 
 1 
 
 2 
 
 ^ 
 
 1 
 
 2 
 
 3 
 
 1 
 
 9 
 
 11 
 
 1 
 
 9 
 
 11 
 
 14 
 
 2 
 
 13 
 
 16 
 
 2 
 
 19 
 
 6 
 
 12 
 
 Weight! 
 
 i 
 
 > 
 
 1 
 
 2 
 
 3 
 
 1 
 
 7 
 
 4 
 
 8 
 
 2 
 
 4 
 
 5 
 
 4 
 
 La(ci,ai)= {d2} 
 L a (c2,ai)= (d3) 
 
 (b) Weights on arcs in G°3 
 
 L a (ci,a2)= {d2} 
 L a (c2,a2)= {d3} 
 
 (c) New Labels 
 Figure 4. End of Iteration 2 
 
30 
 
 Weights 
 
 
 
 
 Weights 
 
 
 Vi 
 
 1 
 
 2 
 
 3 
 
 V 
 
 a\ 
 
 1 
 
 2 
 
 3 
 
 1 
 
 7 
 
 4 
 
 8 
 
 1 
 
 18 
 
 19 
 
 23 
 
 2 
 
 4 
 
 5 
 
 4 
 
 2 
 
 20 
 
 22 
 
 25 
 
 Previous Arcs New Arcs (a') 
 
 (a) Graph G4 (b) Weights on arcs in G°4 
 
 Labels: New Arcs (a') 
 La'(ai,bi)={ci,d2) L a '(ai,b2) ={c2,d3) L a '(ai,D3) ={ci,d2) 
 L a '(a2,bi) ={ci,d2) La'(a2,b2) ={c2,d3) L a '(a2,b3) ={ci,d2) 
 
 Figure 5. End of Iteration 3 
 
 (a) Graph G5 
 
 Weights 
 
 
 
 Vi 
 
 1 
 
 2 
 
 3 
 
 1 
 
 25 
 
 23 
 
 31 
 
 2 
 
 24 
 
 27 
 
 29 
 
 (b) Weights on G° 5 
 
 Labels same as the labels on the New Arcs a' in Iteration 3 
 
 Figure 6. End of Iteration 4 
 
31 
 
 Figure 7. Algorithm SP: The Solution 
 
 Bl 
 
 Figure 8. Series-Parallel Graph G' with a Block B 1 
 
 Graph G 
 Figure 9. Graph G Obtained by Replacing Edge (u,v) in G' by Bl