Document Type : Research Paper


Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran


An extended star is a tree which has only one vertex with degree larger than two. The -center problem in a graph  asks to find a subset  of the vertices of  of cardinality  such that the maximum weighted distances from  to all vertices is minimized. In this paper we consider the -center problem on the unweighted extended stars, and present some properties to find solution.


Main Subjects

[1] Bespamyatnikh S., Bhattacharya B., Keil M., Kirkpatrick D., Segal M., Efficient algorithms for centers and medians in interval and circular-arc graphs, Networks, 39, 144-152, 2002.
[2] Burkard R. E., Dollani H., Center problems with pos/neg weights on trees, European Journal of Operational Research, 145, 483–495, 2003.
[3] Drezner Z., Hamacher H., Facility location: Applications and Theory. Springer-Verlag, Berlin, 2002.
[4] Frederickson G., Parametric search and locating supply centers in trees,  Proceedings of Workshop on Algorithms and Data Structures, 299-319, 1991.
[5] Kariv O., Hakimi S. L., An algorithmic approach to network location problems. Part I: the p-centers,  SIAM J. Appl. Math., 37, 513-538, 1979.
[6] Lan Y. F., Wang Y. L., Suzuki H., A linear-time algorithm for solving the center problem on weighted cactus graphs,  Information Processing Letters, 71, 205-212, 1999.
[7] Mirchandani P. B., Francis R.,  Discrete Location Theory, J.Wiley, 1990.
[8] Tamir A., Improved complexity bounds for center location problems on networks by using dynamic data structures,  SIAM Journal of Discrete Mathematics, 1, 377-396, 1988.