Article ID: | iaor199319 |
Country: | Canada |
Volume: | 30 |
Start Page Number: | 319 |
End Page Number: | 324 |
Publication Date: | May 1992 |
Journal: | INFOR |
Authors: | Aneja Y.P., Nair K.P.K. |
Keywords: | location, networks |
The authors consider the problem of locating a tree shaped facility in an undirected network. If the facility is of obnoxious type the problem is one of finding a tree whose length is at least a stated value such that the minimum of the shortest distances from the nodes on the tree to nodes that are not on the tree is maximum. Analogously, in the case of a friendly facility the authors wish to find a tree whose length is at most a stated value such that the maximum of the above shortest distances is minimum. For the first case they provide a polynomial algorithm but show that the second case belongs to the class of NP-hard problems. Two analogous problems, each involving a path shaped facility, are also shown to be NP-hard.