An improved algorithm for the p-center problem on interval graphs with unit lengths

Edwin Tai Chiu Cheng; Liying Kang; Chi To Ng

doi:10.1016/j.cor.2005.08.013

An improved algorithm for the p-center problem on interval graphs with unit lengths

Edwin Tai Chiu Cheng, Liying Kang, Chi To Ng

Research output: Journal article publication › Journal article › Academic research › peer-review

20 Citations (Scopus)

Abstract

The p-center problem is to locate p facilities in a network of n demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O (n) time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O (pn).

Original language	English
Pages (from-to)	2215-2222
Number of pages	8
Journal	Computers and Operations Research
Volume	34
Issue number	8
DOIs	https://doi.org/10.1016/j.cor.2005.08.013
Publication status	Published - 1 Aug 2007

Keywords

Interval graph
Location
p-center problem

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research

More information

10.1016/j.cor.2005.08.013

http://hdl.handle.net/10397/655

Cite this

@article{48502a3b79e04d22899d14d930498e82,

title = "An improved algorithm for the p-center problem on interval graphs with unit lengths",

abstract = "The p-center problem is to locate p facilities in a network of n demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O (n) time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O (pn).",

keywords = "Interval graph, Location, p-center problem",

author = "Cheng, {Edwin Tai Chiu} and Liying Kang and Ng, {Chi To}",

year = "2007",

month = aug,

day = "1",

doi = "10.1016/j.cor.2005.08.013",

language = "English",

volume = "34",

pages = "2215--2222",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

number = "8",

}

TY - JOUR

T1 - An improved algorithm for the p-center problem on interval graphs with unit lengths

AU - Cheng, Edwin Tai Chiu

AU - Kang, Liying

AU - Ng, Chi To

PY - 2007/8/1

Y1 - 2007/8/1

N2 - The p-center problem is to locate p facilities in a network of n demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O (n) time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O (pn).

AB - The p-center problem is to locate p facilities in a network of n demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O (n) time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O (pn).

KW - Interval graph

KW - Location

KW - p-center problem

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

U2 - 10.1016/j.cor.2005.08.013

DO - 10.1016/j.cor.2005.08.013

M3 - Journal article

SN - 0305-0548

VL - 34

SP - 2215

EP - 2222

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 8

ER -

An improved algorithm for the p-center problem on interval graphs with unit lengths

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this