| 树网络上的连通p-median问题 |
| |
| 引用本文： | 陈光亭,丁蔚,李守伟.树网络上的连通p-median问题[J].杭州电子科技大学学报,2009,29(2). |
| |
| 作者姓名： | 陈光亭 丁蔚 李守伟 |
| |
| 作者单位： | 杭州电子科技大学运筹与控制研究所,浙江,杭州,310018 |
| |
| 摘 要： | 给定一个连通图G=(V,E),每一个顶点和边都赋予一个非负的权重,传统的p-median问题是要找出V的一个包含p个点的子集H,使得其余各点到H的赋权距离和最小。如果要求由H导出的子图是连通的,则称之为连通p-median问题。该文研究树网络上的连通p-median问题,给出了一个O(pn)的算法,随后把该算法推广到带有禁选点的树网络上。
|
| 关 键 词： | 连通图 动态规划 树网络 |
Connected P- median Problems in Tree Networks |
| |
| CHEN Guang-fing,DING Wei,LI Shou-wei.Connected P- median Problems in Tree Networks[J].Journal of Hangzhou Dianzi University,2009,29(2). |
| |
| Authors: | CHEN Guang-fing DING Wei LI Shou-wei |
| |
| Affiliation: | CHEN Guang-ting; DING Wei; LI Shou-wei (Institute of Operational Research and Cybernetics; Hangzhou Dianzi University; Hangzhou Zhejiang 310018; China); |
| |
| Abstract: | 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. |
| |
| Keywords: | connected graph dynamic programming tree networks |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
