The 2-radius and 2-radiian problems on trees

Hung Lung Wang, Kun Mao Chao*

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

摘要

In this paper, we consider two facility location problems on tree networks. One is the 2-radius problem, whose goal is to partition the vertex set of the given network into two non-empty subsets such that the sum of the radii of these two induced subgraphs is minimum. The other is the 2-radiian problem, whose goal is to partition the network into two non-empty subsets such that the sum of the centdian values of these two induced subgraphs is minimum. We propose an O (n)-time algorithm for the 2-radius problem on trees and an O (n log n)-time algorithm for the 2-radiian problem on trees, where n is the number of vertices in the given tree.

原文英語
頁(從 - 到)524-531
頁數8
期刊Theoretical Computer Science
407
發行號1-3
DOIs
出版狀態已發佈 - 2008 11月 6
對外發佈

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「The 2-radius and 2-radiian problems on trees」主題。共同形成了獨特的指紋。

引用此