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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 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 languageEnglish
Pages (from-to)2215-2222
Number of pages8
JournalComputers and Operations Research
Volume34
Issue number8
DOIs
Publication statusPublished - 1 Aug 2007

Keywords

  • Interval graph
  • Location
  • p-center problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this