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 条
  • [11] The inverse 1-median problem on a cycle
    Burkard, Rainer E.
    Pleschiutschnig, Carmen
    Zhang, Jianzhong
    DISCRETE OPTIMIZATION, 2008, 5 (02) : 242 - 253
  • [12] On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks
    Kien Trung Nguyen
    Huong Nguyen-Thu
    Nguyen Thanh Hung
    Mathematical Methods of Operations Research, 2018, 88 : 147 - 159
  • [13] Some Polynomially Solvable Cases of the Inverse Ordered 1-Median Problem on Trees
    Kien Trung Nguyen
    FILOMAT, 2017, 31 (12) : 3651 - 3664
  • [14] The 1-median and 1-highway problem
    Diaz-Banez, J. M.
    Korman, M.
    Perez-Lantero, P.
    Ventura, I.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 225 (03) : 552 - 557
  • [15] On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks
    Kien Trung Nguyen
    Huong Nguyen-Thu
    Nguyen Thanh Hung
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2018, 88 (02) : 147 - 159
  • [16] The Connected P-Median Problem on Cactus Graphs
    Bai, Chunsong
    Zhou, Jianjie
    Liang, Zuosong
    COMPUTATIONAL INTELLIGENCE AND NEUROSCIENCE, 2021, 2021
  • [17] THE EXTENSIVE 1-MEDIAN PROBLEM WITH RADIUS ON NETWORKS
    Tran Hoai Ngoc Nhan
    Nguyen Thanh Hung
    Kien Trung Nguyen
    OPUSCULA MATHEMATICA, 2024, 44 (01) : 135 - 149
  • [18] INVERSE GROUP 1-MEDIAN PROBLEM ON TREES
    Kien Trung Nguyen
    Vo Nguyen Minh Hieu
    Van Huy Pham
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2021, 17 (01) : 221 - 232
  • [19] LEXICOGRAPHIC α-ROBUSTNESS: AN APPLICATION TO THE 1-MEDIAN PROBLEM
    Kalai, R.
    Aloulou, M. A.
    Vallin, Ph.
    Vanderpooten, D.
    RAIRO-OPERATIONS RESEARCH, 2010, 44 (02) : 119 - 138
  • [20] The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance
    Kien Trung Nguyen
    Chassein, Andre
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 247 (03) : 774 - 781
12345