Paper Info
Title
The 2-radius and 2-radiian problems on trees
Abstract
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(nlogn)-time algorithm for the 2-radiian problem on trees, where n is the number of vertices in the given tree.
Year
DOI
Venue
2008
10.1016/j.tcs.2008.08.022
Theor. Comput. Sci.
Keywords
DocType
Volume
tree network,Radiian,radiian,2-radius problem,centdian value,Median,center,centdian,2-radiian problem,facility location problem,median,Radius,tree,Tree,induced subgraphs,Facility location problem,Center,radius,time algorithm,Centdian
Journal
407
Issue
ISSN
Citations 
1-3
Theoretical Computer Science
0
PageRank 
References 
Authors
0.34
13
2
Name
Order
Citations
PageRank
Hung-Lung Wang1275.63
Kun-mao Chao283894.05