The 2-Median Problem on Cactus Graphs with Positive and Negative Weights

被引：0
作者：
Bai, Chunsong [1 ]
Kang, Liying [2 ]
机构：
[1] Fuyang Normal Univ, Coll Math, Fuyang 236041, Peoples R China
[2] Shanghai Univ, Dept Math, Shanghai 200444, Peoples R China
来源：
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I | 2017年 / 10627卷
关键词：
Location problem; Median problem; Cactus graphs; Obnoxious facility;
D O I：
10.1007/978-3-319-71150-8_24
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper studies the problem of locating two vertices in a cactus with positive and negative vertex weights. The problem has objective to minimize the sum of minimum weighted distances from every vertex of the cactus to the two medians. We develop an O(n(2)) algorithm for the 2-median problem, where n is the number of vertices of the cactus.
引用
收藏
页码：278 / 285
页数：8
相关论文
共 6 条
1