Location of a tree shaped facility in a network

Location of a tree shaped facility in a network

0.00 Avg rating0 Votes
Article ID: iaor199319
Country: Canada
Volume: 30
Start Page Number: 319
End Page Number: 324
Publication Date: May 1992
Journal: INFOR
Authors: ,
Keywords: location, networks
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.