The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers |
| |
| Authors: | Chun-song Bai Li-ying Kang |
| |
| Institution: | 1.Department of Mathematics,Fuyang Normal College,Fuyang,China;2.Department of Mathematics,Shanghai University,Shanghai,China |
| |
| Abstract: | 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 log n) for the problem on a balanced tree, where n is the number of the vertices in the tree. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
