摘要
给定一个连通图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.
出处
《杭州电子科技大学学报(自然科学版)》
2009年第2期89-91,共3页
Journal of Hangzhou Dianzi University:Natural Sciences
基金
国家自然科学基金资助项目(10371028)
关键词
连通图
动态规划
树网络
connected graph
dynamic programming
tree networks