Unweighted p-center problem on extended stars

Subject Areas : Mathematical Engineering

Jafar Fathali ¹ , Nader Jafari Rad ² , Sadegh Rahimi Sherbaf ³

1 -
2 -
3 -

Received: 2014-01-20 Accepted : 2014-04-20 Published : 2014-07-01

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.

References:

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