|
|||||
|
|
| The Backup 2-Median Problem on Block Graphs | |
| 作者姓名： | Yu-kun CHENG Li-ying KANG Hong YAN |
| 基金项目： | Supported by the National Natural Science Foundation of China （No. 11301475, 11126202, 11171207）, the Nature Science Foundation of Zhejiang Province （No. LQ12A01011） and partially supported by The Hong Kong CERG Research Fund PolyU 5515/10H. |
| 摘 要： | The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph. |
| 关 键 词： | 备份 中位 定位问题 块图 顶点 设备 设施 故障 |
The backup 2-median problem on block graphs |
|
| Yu-kun CHENG,Li-ying KANG,Hong YAN.The Backup 2-Median Problem on Block Graphs[J].Acta Mathematicae Applicatae Sinica,2014,30(2):309-320. | |
| Authors: | Yu-kun Cheng Li-ying Kang Hong Yan |
| Institution: | 1. Zhejiang University of Finance and Economics, Hangzhou, 310018, China 2. Department of Mathematics, Shanghai University, Shanghai, 200444, China 3. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, HKSAR, Hong Kong, China |
| Abstract: | The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O(n log n+m)-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph. |
| Keywords: | location theory backup median block graph |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ | |