树网络上的连通p-median问题

Connected P-median Problems in Tree Networks

给定一个连通图G=(V,E),每一个顶点和边都赋予一个非负的权重,传统的p-median问题是要找出V的一个包含p个点的子集H,使得其余各点到H的赋权距离和最小。如果要求由H导出的子图是连通的,则称之为连通p-median问题。该文研究树网络上的连通p-median问题,给出了一个O(pn)的算法,随后把该算法推广到带有禁选点的树网络上。

Given a connected graph,there is a nonnegative weight for every vertex and edge.The general-median problem of this graph is to find a subset with vertices and such that the sum of weighted distance from every vertex tois minimum.If the induced subgraph of is connected,then we call the problem as connected-median problem.We study the connected-median problems in tree networks,an algorithm is presented.We then generalize this algorithm to the situation with some forbidden vertices.