The Pos/neg-weighted 2-medians in Balanced Trees with Subtree-shaped Customers  

作　　者：Chun-song BAI Li-ying KANG 

机构地区：[1]Department of Mathematics,Fuyang Normal College [2]Department of Mathematics,Shanghai University

出　　处：《Acta Mathematicae Applicatae Sinica》2016年第4期891-898,共8页应用数学学报（英文版）

基　　金：Supported by the National Nature Science Foundation of China(Nos.11471210,11571222)

摘　　要：This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O（n logn） for the problem on a balanced tree, where n is the number of the vertices in the tree.This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O（n logn） for the problem on a balanced tree, where n is the number of the vertices in the tree.

关 键 词：Location problems subtree-shaped customers obnoxious facilities 

分 类 号：O157.5[理学—数学]