The Backup 2-Median Problem on Block Graphs  

作　　者：Yu-kun CHENG Li-ying KANG Hong YAN 

机构地区：[1]Zhejiang University of Finance and Economics [2]Department of Mathematics,Shanghai University [3]Department of Logistics and Maritime Studies,The Hong Kong Polytechnic University

出　　处：《Acta Mathematicae Applicatae Sinica》2014年第2期309-320,共12页应用数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China(No.11301475,11126202,11171207);the Nature Science Foundation of Zhejiang Province(No.LQ12A01011);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 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.

关 键 词：location theory BACKUP MEDIAN block graph 

分 类 号：O157.5[理学—数学] TP311.13[理学—基础数学]