A combinatorial algorithm for the ordered 1-median problem on cactus graphs

被引：0

作者：

Van Huy Pham ^{[1
]}

Nguyen Chi Tam ^{[2
]}

机构：

[1] Ton Duc Thang Univ, Fac Informat Technol, AI Lab, Ho Chi Minh City, Vietnam

[2] Can Tho Univ, Dept Math, Teacher Coll, Can Tho, Vietnam

来源：

OPSEARCH | 2019年 / 56卷 / 03期

关键词：

Location problem; Ordered; 1-median; Cactus; Convex; NETWORK LOCATION PROBLEMS;

D O I：

10.1007/s12597-019-00402-2

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Cactus graph is a graph in which any two simple cycles has at most one vertex in common. In this paper we address the ordered 1-median location problem on cactus graphs, a generalization of some popular location models such as 1-median, 1-center, and 1-centdian problems. For the case with non-decreasing multipliers, we show that there exists a cycle or an edge that contains an ordered 1-median. Based on this property, we develop a combinatorial algorithm that finds an ordered 1-median on a cactus in O(n(2) logn) time, where n is the number of vertices in the underlying cactus.

引用

页码：780 / 789

页数：10