This paper concerns the problem of locating a central facility on a connected, undirected network. The network, N, could be representative of a transport system and the central facility takes the form of a connected subgraph of N. The problem is to locate a central facility that provides services to demands located at the vertices of the network. Two types of costs are involved with a given facility location. The first cost is the setup cost of establishing a facility, proportional to the length of the facility. The second cost is the cost of providing service, which is defined to be the weighted distance from each demand point to the facility. A linear time algorithm is presented for the problem on a tree. The problem on a general network is NP-hard, but under certain special cases, efficient algorithms are available.
