Journal article
Locating A Median Subtree On A Network
INFOR. Information systems and operational research, Vol.29(2), pp.153-166
05/01/1991
DOI: 10.1080/03155986.1991.11732163
Abstract
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 vith 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.
Details
- Title: Subtitle
- Locating A Median Subtree On A Network
- Creators
- Tae Ung Kim - Sungkyunkwan UniversityTimothy J. Lowe - University of IowaJames E. Ward - Purdue University West Lafayette
- Resource Type
- Journal article
- Publication Details
- INFOR. Information systems and operational research, Vol.29(2), pp.153-166
- DOI
- 10.1080/03155986.1991.11732163
- ISSN
- 0315-5986
- eISSN
- 1916-0615
- Publisher
- Taylor & Francis
- Number of pages
- 14
- Language
- English
- Date published
- 05/01/1991
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963077702771
Metrics
1 Record Views