Unweighted p-center problem on extended stars
Subject Areas : Mathematical EngineeringJafar Fathali 1 , Nader Jafari Rad 2 , Sadegh Rahimi Sherbaf 3
1 - Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran
2 - Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran
3 - Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran
Keywords: Location theory, center problem, extended star,
Abstract :
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.
[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.