The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs |
| |
| Authors: | Shun-Chieh Chang William Chung-Kung Yen Yue-Li Wang Jia-Jie Liu |
| |
| Institution: | 1.Department of Information Management,National Taiwan University of Science and Technology,Taipei,Taiwan;2.Department of Information Management,Shih Hsin University,Taipei,Taiwan |
| |
| Abstract: | In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
