Abstract
In this paper, we consider the problems of locating p-vertex \(X_p\) on block graphs such that the induced subgraph of the selected p vertices is connected. Two problems are proposed: one problem is to minimizes the sum of its weighted distances from all vertices to \(X_p\), another problem is to minimize the maximum distance from each vertex in \(V-X_p\) to \(X_p\) and at the same time to minimize the sum of its distances from all vertices. 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.
Research was partially supported by the National Nature Science Foundation of China (Nos. 11471210, 11571222).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Averbakh, I., Berman, O.: Algorithms for path medi-centers of a tree. Comput. Oper. Res. 26, 1395–1409 (1999)
Becker, R.I., Lari, I., Scozzari, A.: Algorithms for central-median paths with bounded length on trees. Eur. J. Oper. Res. 179, 1208–1220 (2007)
Behtoei, A., Jannesari, M., Tseri, B.: A characterization of block graphs. Discrete Appl. Math. 158, 219–221 (2010)
Chen, M.L., Francis, R.L., Lawrence, J.F., Lowe, T.J., Tufekci, S.: Block-vertex duality and the one-median problem. Networks 15, 395–412 (1985)
Halpern, J.: The location of a cent-dian convex combination on an undirected tree. J. Reg. Sci. 16, 237–245 (1976)
Halpern, J.: Finding minimal center-median combination (Cent-Dian) of a graph. Manage. Sci. 24, 535–544 (1978)
Handler, G.Y.: Medi-centers of a tree. Transp. Sci. 19, 246–260 (1985)
Hansen, P., LabbeH, M., Thisse, J.-F.: From the median to the generalized center. Oper. Res. 25, 73–86 (1991)
Tamir, A., Puerto, J., Pérez-Brito, D.: The centdian subtree on tree networks. Discrete Appl. Math. 118, 263–278 (2002)
Shan, E., Zhou, J., Kang, L.: The connected \(p\)-center and p-median problems on interval and circular-arc graphs. Acta Mathematicae Applicatae Sinica (Accepted)
Yen, W.C.-K.: The connected \(p\)-center problem on block graphs with forbidden vertices. Theor. Comput. Sci. 426, 13–24 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kang, L., Zhou, J., Shan, E. (2015). The Connected p-Centdian Problem on Block Graphs. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science(), vol 9486. Springer, Cham. https://doi.org/10.1007/978-3-319-26626-8_37
Download citation
DOI: https://doi.org/10.1007/978-3-319-26626-8_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26625-1
Online ISBN: 978-3-319-26626-8
eBook Packages: Computer ScienceComputer Science (R0)