块图中的无权1-中心问题

张晓芹, 康丽英

doi:10.3969/j.issn.1007-2861.2011.03.008

上海大学学报(自然科学版) >

2011 , Vol. 17 >Issue 3: 259 - 262

DOI: https://doi.org/10.3969/j.issn.1007-2861.2011.03.008

数理化科学

块图中的无权1-中心问题

展开

上海大学理学院,上海 200444

康丽英（1965~），女，教授，博士生导师,研究方向为图论与组合优化. Email:lykang@shu.edu.cn

收稿日期: 2010-01-12

网络出版日期: 2011-06-24

基金资助

上海大学创新基金资助项目(SHUCX092012);国家自然科学基金资助项目(10971131);上海市重点学科建设资助项目(S30104)〖JP〗

收起

Unweighted 1-Center Problem on Block Graphs

Expand

College of Sciences, Shanghai University, Shanghai 200444, China

Received date: 2010-01-12

Online published: 2011-06-24

Fold

摘要

p中心问题是指在网络图中放置p个设施，使得每个客户到达最近设施的最大权距离最小.如果所有客户的权值均为1，则称为无权中心问题.主要研究边长为1的块图中的无权1-中心问题,借助于块图树形轮廓的构造，该问题在线性时间内可得以解决.

关键词： 块图; 网络图; 选址问题; 中心问题

本文引用格式

张晓芹, 康丽英 . 块图中的无权1-中心问题[J]. 上海大学学报(自然科学版), 2011 , 17(3) : 259 -262 . DOI: 10.3969/j.issn.1007-2861.2011.03.008

Abstract

In the pcenter problem, p facilities are located in the network such that the maximum weighted distance from a client to its nearest facility is minimized. If all client weights are equal to 1, it is called an unweighted center problem. Unweighted 1-center problem is studied on block graphs with a unit edge length. It is shown that the problem can be solved in linear time using the tree structure of a block graph.

Key words： block graph; center problem; location problems; networks

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract