Chiang Mai Journal of Science, Faculty of Science, Chiang Mai University

Visitors
ALL : 2,095,319
TODAY : 3,663
ONLINE : 222

JOURNAL DETAIL

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:506 Download:168

Algorithmic Results of Independent k-Domination on Weighted Graphs
page: 58 - 70
Author:William C-K. Yen
Vol.38 (SPECIAL ISSUE 2011) View: 574 Download:122

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