The 2-radius and 2-radiian problems on trees
Resource
Theoretical Computer Science 407 (1-3): 524-531
Journal
Theoretical Computer Science
Journal Volume
407
Journal Issue
1-3
Pages
524-531
Date Issued
2008
Date
2008
Author(s)
Wang, Hung-Lung
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 (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.
Subjects
Centdian; Center; Facility location problem; Median; Radiian; Radius; Tree
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
17.pdf
Size
757.8 KB
Format
Adobe PDF
Checksum
(MD5):71d9dc174ef17320b355f8d4b9b4ad0f