Journal Volumes


Visitors
ALL : 2,314,963
TODAY : 8,263
ONLINE : 397

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

  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: 596 Download:138



Search in this journal


Document Search


Author Search

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Popular Search






Chiang Mai Journal of Science

Faculty of Science, Chiang Mai University
239 Huaykaew Road, Tumbol Suthep, Amphur Muang, Chiang Mai 50200 THAILAND
Tel: +6653-943-467




Faculty of Science,
Chiang Mai University




EMAIL
cmjs@cmu.ac.th




Copyrights © Since 2021 All Rights Reserved by Chiang Mai Journal of Science