The backup 2-median problem on block graphs

Yu kun Cheng, Li ying Kang, Hong Yan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O(n log n+m)-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.
Original languageEnglish
Pages (from-to)309-320
Number of pages12
JournalActa Mathematicae Applicatae Sinica
Volume30
Issue number2
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • backup
  • block graph
  • location theory
  • median

ASJC Scopus subject areas

  • Applied Mathematics

Cite this