Abstract | ||
---|---|---|
The network version of them-median problem with mutual communication (MMMC) is to find the location ofm new facilities on a network withn nodes such that the sum of (a) the cost of interaction between the new facilities andn existing facilities on the network, and (b) the 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. This problem is shown to be equivalent to a graph-theoretic Node Selection Problem
(NSP). We show that many other problems can be formulated as an NSP. We then provide a polynomial time algorithm to solve
NSP for the case when the flow graph is Halin. Extensions to other graph families are provided. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1007/BF02060472 | Annals of Operations Research |
Keywords | Field | DocType |
Polynomial Time Algorithm,Flow Graph,Network Distance,Outerplanar Graph,Parallel Reduction | Discrete mathematics,Graph,Mathematical optimization,Outerplanar graph,Control flow graph,Time complexity,Mathematics | Journal |
Volume | Issue | Citations |
40 | 1-4 | 3 |
PageRank | References | Authors |
0.44 | 13 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dilip Chhajed | 1 | 339 | 27.21 |
Timothy J. Lowe | 2 | 377 | 39.67 |