Abstract
We consider the facility location problem of locating a set \(X_p\) of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set \(X_p\) is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to \(X_p\), another problem is to minimize the maximum distance from each vertex that is not in \(X_p\) to \(X_p\) and, at the same time, to minimize the sum of its distances from all vertices of G to \(X_p\). We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in \(O(n^2)\) time, where n is the number of vertices of the block graph G.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Averbakh I, Berman O (1999) Algorithms for path medi-centers of a tree. Comput Oper Res 26:1395–1409
Becker RI, Lari I, Scozzari A (2007) Algorithms for central-median paths with bounded length on trees. Eur J Oper Res 179:1208–1220
Behtoei A, Jannesari M, Tseri B (2010) A characterization of block graphs. Discret Appl Math 158:219–221
Chen ML, Francis RL, Lawrence JF, Lowe TJ, Tufekci S (1985) Block-vertex duality and the one-median problem. Networks 15:395–412
Halpern J (1976) The location of a cent-dian convex conbination on an undirected tree. J Reg Sci 16:237–245
Halpern J (1978) Finding minimal center-median combination (cent-dian) of a graph. Manag Sci 24:535–544
Handler GY (1985) Medi-centers of a tree. Transp Sci 19:246–260
Hansen P, Labbe M, Thisse J-F (1991) From the median to the generalized center. Oper Res 25:73–86
Shan E, Zhou J, Kang L The connected \(p\)-center and \(p\)-median problems on interval and circular-arc graphs. Acta Math Appl Sin (to appear)
Tamir A, Puerto J, Pérez-Brito D (2002) The centdian subtree on tree networks. Discret Appl Math 118:263–278
Yen WC-K (2012) The connected \(p\)-center problem on block graphs with forbidden vertices. Theor Comput Sci 426:13–24
Acknowledgments
Research was partially supported by the National Nature Science Foundation of China (Nos. 11471210 and 11571222)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kang, L., Zhou, J. & Shan, E. Algorithms for connected p-centdian problem on block graphs. J Comb Optim 36, 252–263 (2018). https://doi.org/10.1007/s10878-016-0058-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0058-0