Submit your paper 
Download Template JOURNAL DETAIL
The NP-Hardness of the Connected p-Median Problem on Bipartite Graphs and Split Graphs*
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., Chung-Kung W., 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. |
SDGs |
|
| View:581 Download:203 | |
RELATED ARTICLE
Algorithmic Results of Independent k-Domination on Weighted Graphs
page: 58 - 70
Author:William C-K. Yen
Vol.38 (SPECIAL ISSUE 2011) View: 644 Download:153
page: 58 - 70
Author:William C-K. Yen
Vol.38 (SPECIAL ISSUE 2011) View: 644 Download:153
Copyrights © Since 2021 All Rights Reserved by Chiang Mai Journal of Science