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

doi:10.3969/j.issn.1007-2861.2011.03.008

上海大学学报(自然科学版) ›› 2011, Vol. 17 ›› Issue (3): 259-262.doi: 10.3969/j.issn.1007-2861.2011.03.008

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

上海大学理学院,上海 200444

收稿日期:2010-01-12 出版日期:2011-06-24 发布日期:2011-06-24
通讯作者: 康丽英（1965~），女，教授，博士生导师,研究方向为图论与组合优化. Email:lykang@shu.edu.cn
作者简介:康丽英（1965~），女，教授，博士生导师,研究方向为图论与组合优化. Email:lykang@shu.edu.cn
基金资助:
上海大学创新基金资助项目(SHUCX092012);国家自然科学基金资助项目(10971131);上海市重点学科建设资助项目(S30104)〖JP〗

Unweighted 1-Center Problem on Block Graphs

College of Sciences, Shanghai University, Shanghai 200444, China

Received:2010-01-12 Online:2011-06-24 Published:2011-06-24

摘要/Abstract

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

关键词: 块图, 网络图, 选址问题, 中心问题

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

中图分类号:

O 157.6

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

ZHANG Xiao-Qin, KANG Li-Yang. Unweighted 1-Center Problem on Block Graphs[J]. Journal of Shanghai University（Natural Science Edition）, 2011, 17(3): 259-262.

[1]	张茜1,2, 金翊1,2,3, 宋凯1,2, 高桓1,2. 三值光学计算机MPI编程技术在超算集群中的使用[J]. 上海大学学报(自然科学版), 2014, 20(2): 180-189.
[2]	秦世伟, 莫泷, 周艳坤. 静压桩沉桩及已打入桩遮拦效应的数值模拟[J]. 上海大学学报(自然科学版), 2014, 20(2): 239-249.
[3]	徐秦乐1, 张金艺1,2,3, 徐惠政1, 李若涵2, 张晶晶2. 高精度故障电弧检测多传感器数据融合算法[J]. 上海大学学报(自然科学版), 2014, 20(2): 165-173.
[4]	黄青华, 李琳, 赖士村. 基于 RBF 神经网络的头相关传输函数的个性化建模方法[J]. 上海大学学报(自然科学版), 2014, 20(2): 157-164.
[5]	曹绍梅, 张大卫, 冯欣, 迟涛, 施利毅. 尖晶石结构Li₄Ti₅O₁₂的制备及其电化学性能[J]. 上海大学学报(自然科学版), 2012, 18(6): 572-576.
[6]	张翔, 郝雷, 王卿文. 矩阵方程组中心对称解的极秩[J]. 上海大学学报(自然科学版), 2012, 18(6): 596-600.
[7]	李东兵，李国平，滕国伟，赵海武，王国中,李萍. 一种新的自适应维纳滤波方法[J]. 上海大学学报(自然科学版), 2012, 18(6): 555-560.
[8]	钱佳民，徐闰，汤敏燕. 小尺度薄型封装焊点失效机理和可靠性设计[J]. 上海大学学报(自然科学版), 2012, 18(6): 561-566.
[9]	刘婧颖, 谢耀平, 陈业新, 黄晓君, 赵世金. H和B原子在有序态 Ni₃Fe 表面的吸附[J]. 上海大学学报(自然科学版), 2012, 18(6): 567-571.
[10]	崔泽, 韩增军. 基于自运动的仿人七自由度机械臂逆解算法[J]. 上海大学学报(自然科学版), 2012, 18(6): 589-605.
[11]	郭路军. p-余弦变换及其在凸几何分析中的应用[J]. 上海大学学报(自然科学版), 2012, 18(6): 601-605.
[12]	江金胜, 董力耘. 信号灯交叉口处综合待行区的建模与模拟[J]. 上海大学学报(自然科学版), 2012, 18(6): 606-611.
[13]	蔡茂源，张田忠. 多壁碳纳米管压缩与弯曲时屈曲的ANSYS模拟[J]. 上海大学学报(自然科学版), 2012, 18(6): 612-616.
[14]	时伉丽, 丁虎, 陈立群, 储德林. 移动载荷黏弹性Pasternak地基梁动力学响应[J]. 上海大学学报(自然科学版), 2012, 18(6): 617-621.
[15]	沈佳铖，任九生. 动脉壁的动力响应特性[J]. 上海大学学报(自然科学版), 2012, 18(6): 622-626.

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

Unweighted 1-Center Problem on Block Graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价