The NP-Hardness of the Connected p-Median Problem on Bipartite Graphs and Split Graphs*
Shun-Chieh Chang1, William Chung-Kung Yen2, Yue-Li Wang1, and Jia-Jie Liu2* Author for corresponding; e-mail address: ckyen001@ms7.hinet.net
Volume: Vol.40 No.1 (JANUARY 2013)
Research Article
DOI:
Received: 28 June 2011, Revised: -, Accepted: 29 April 2012, Published: -
Citation: Chang1 S., Yen2 W.C., Wang1 Y. and Liu2 J., The NP-Hardness of the Connected p-Median Problem on Bipartite Graphs and Split Graphs*, Chiang Mai Journal of Science, 2013; 40(1): 83-88.
Abstract
In this paper, we study a variant of the p-median problem on graphs in which the subgraph induced by the p-median is asked to be connected, and this problem is called the connected p-median problem. We show that the connected p-median problem is NP-hard on bipartite graphs and split graphs, respectively.