The connected p-median problem on block graphs

详细信息    查看全文

• 作者：Shun-Chieh Chang ; William Chung-Kung Yen ; Yue-Li Wang ; Jia-Jie Liu
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：10
• 期：6
• 页码：1191-1201
• 全文大小：471 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480
• 卷排序：10

文摘

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.KeywordsGraph theoryConnected p-medianComplete graphsBlock graphsNP-hard