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
相关论文
共 50 条
  • [1] A combinatorial algorithm for the ordered 1-median problem on cactus graphs
    Van Huy Pham
    Nguyen Chi Tam
    OPSEARCH, 2019, 56 : 780 - 789
  • [2] An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs
    Lan, YF
    Wang, YL
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 122 (03) : 602 - 610
  • [3] A combinatorial algorithm for the 1-median problem in Rd with the Chebyshev norm
    Hatzl, Johannes
    Karrenbauer, Andreas
    OPERATIONS RESEARCH LETTERS, 2010, 38 (05) : 383 - 385
  • [4] A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
    Burkard, RE
    Krarup, J
    COMPUTING, 1998, 60 (03) : 193 - 215
  • [5] A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
    R. E. Burkard
    J. Krarup
    Computing, 1998, 60 : 193 - 215
  • [6] An Efficient Approximate Algorithm for the 1-Median Problem on a Graph
    Tabata, Koji
    Nakamura, Atsuyoshi
    Kudo, Mineichi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2017, E100D (05): : 994 - 1002
  • [7] A linear time algorithm for the reverse 1-median problem on a cycle
    Burkard, Rainer E.
    Gassner, Elisabeth
    Hatzl, Johannes
    NETWORKS, 2006, 48 (01) : 16 - 23
  • [8] Inverse 1-Median Problem on Block Graphs with Variable Vertex Weights
    Kien Trung Nguyen
    Journal of Optimization Theory and Applications, 2016, 168 : 944 - 957
  • [9] Inverse 1-Median Problem on Block Graphs with Variable Vertex Weights
    Kien Trung Nguyen
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2016, 168 (03) : 944 - 957
  • [10] Efficient approximate algorithm for the 1-median problem in metric spaces
    Cantone, D
    Cincotti, G
    Ferro, A
    Pulvirenti, A
    SIAM JOURNAL ON OPTIMIZATION, 2005, 16 (02) : 434 - 451
12345