A minimum length covering subgraph of a network |
| |
Authors: | Tae Ung Kim Timothy J Lowe James E Ward Richard L Francis |
| |
Institution: | (1) Sung Kyun Kwan University, Seoul, Korea;(2) Purdue University, West Lafayette, IN, U.S.A.;(3) University of Florida, Gainesville, FL, U.S.A. |
| |
Abstract: | This paper concerns the problem of locating a central facility on a connected networkN. The network,N, could be representative of a transport system, while the central facility takes the form of a connected subgraph ofN. The problem is to locate a central facility of minimum length so that each of several demand points onN is covered by the central facility: a demand point atv
i
inN is covered by the central facility if the shortest path distance betweenv
i
and the closest point in the central facility does not exceed a parameterr
i
. This location problem is NP-hard, but for certain special cases, efficient solution methods are available. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|