Paper Type |
Contributed Paper |
Title |
The NP-Hardness of the Connected p-Median Problem on Bipartite Graphs and Split Graphs* |
Author |
Shun-Chieh Chang1, William Chung-Kung Yen2, Yue-Li Wang1, and Jia-Jie Liu2 |
Email |
ckyen001@ms7.hinet.net |
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. |
|
Start & End Page |
83 - 88 |
Received Date |
2011-06-28 |
Revised Date |
|
Accepted Date |
2012-04-29 |
Full Text |
Download |
Keyword |
Connected p-median, NP-hard, bipartite graph, split graph |
Volume |
Vol.40 No.1 (JANUARY 2013) |
DOI |
|
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 J. Sci., 2013; 40(1): 83-88. |
SDGs |
|
View:530 Download:186 |