Unweighted p-center problem on extended stars

Iranian Journal of Optimization

مقاله 2، دوره 6، شماره 2، مهر 2014، صفحه 737-744   

نوع مقاله: Research Paper

نویسندگان

Jafar Fathali^* ؛ Nader Jafari Rad؛ Sadegh Rahimi Sherbaf

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.

کلیدواژه‌ها

Location theory؛ center problem؛ extended star

مراجع

[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.