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 ...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.展开更多
基金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.
