The 2-radius and 2-radiian problems on trees

Hung Lung Wang; Kun Mao Chao

doi:10.1016/j.tcs.2008.08.022

The 2-radius and 2-radiian problems on trees

Hung Lung Wang, Kun Mao Chao^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	524-531
Number of pages	8
Journal	Theoretical Computer Science
Volume	407
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2008.08.022
Publication status	Published - 2008 Nov 6
Externally published	Yes

Keywords

Centdian
Center
Facility location problem
Median
Radiian
Radius
Tree

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2008.08.022

Cite this

@article{780e9dfc234e47c5afe6186dc4b63137,

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 (n log n)-time algorithm for the 2-radiian problem on trees, where n is the number of vertices in the given tree.",

keywords = "Centdian, Center, Facility location problem, Median, Radiian, Radius, Tree",

author = "Wang, {Hung Lung} and Chao, {Kun Mao}",

year = "2008",

month = nov,

day = "6",

doi = "10.1016/j.tcs.2008.08.022",

language = "English",

volume = "407",

pages = "524--531",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - The 2-radius and 2-radiian problems on trees

AU - Wang, Hung Lung

AU - Chao, Kun Mao

PY - 2008/11/6

Y1 - 2008/11/6

N2 - 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.

AB - 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.

KW - Centdian

KW - Center

KW - Facility location problem

KW - Median

KW - Radiian

KW - Radius

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=53249128849&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=53249128849&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2008.08.022

DO - 10.1016/j.tcs.2008.08.022

M3 - Article

AN - SCOPUS:53249128849

SN - 0304-3975

VL - 407

SP - 524

EP - 531

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

The 2-radius and 2-radiian problems on trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this