https://scholars.lib.ntu.edu.tw/handle/123456789/117603
標題: | The 2-radius and 2-radiian problems on trees | 作者: | Wang, Hung-Lung KUN-MAO CHAO |
關鍵字: | Centdian; Center; Facility location problem; Median; Radiian; Radius; Tree | 公開日期: | 2008 | 卷: | 407 | 期: | 1-3 | 起(迄)頁: | 524-531 | 來源出版物: | Theoretical Computer Science | 摘要: | 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. © 2008 Elsevier B.V. All rights reserved. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/154561 https://www.scopus.com/inward/record.uri?eid=2-s2.0-53249128849&doi=10.1016%2fj.tcs.2008.08.022&partnerID=40&md5=65415f38541e977edfe4e06a5a8f5100 |
ISSN: | 03043975 | DOI: | 10.1016/j.tcs.2008.08.022 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。