Journal article
Block‐vertex duality and the one‐median problem
Networks, Vol.15(4), pp.395-412
1985
DOI: 10.1002/net.3230150402
Abstract
The w-centroid problem, denoted by (C), is an optimization problem which has been shown by Kariv and Hakimi to be equivalent, on a tree graph, to the 1-median location problem, denoted by (M). For a general (weighted) connected graph G we develop a duality between (C) (which is defined on G) and a block optimization problem, denoted by (B), and defined over the blocks of G. A block is a maximal nonseparable subgraph. We analyze (B) and (C) by means of two problems equivalent to (B) and (C) respectively, but defined on a blocking graph G which is always a tree. We give an O(∣V∣) algorithm to solve the two problems on G, and we characterize the solutions. We also show that the solution to a 1-median problem defined on G either solves (M) on the original graph G or localizes the search for a solution to (M) to the vertices of a single block. We introduce an extended version of Goldman's algorithm which (in linear time) either solves (M) on G, or finds the single block of G which contains all solutions to (M).
Details
- Title: Subtitle
- Block‐vertex duality and the one‐median problem
- Creators
- M. ‐L Chen - North Carolina State UniversityR. L. Francis - University of FloridaJ. F. Lawrence - George Mason UniversityT. J. Lowe - Purdue University West LafayetteS. Tufekci - University of Florida
- Resource Type
- Journal article
- Publication Details
- Networks, Vol.15(4), pp.395-412
- DOI
- 10.1002/net.3230150402
- ISSN
- 0028-3045
- eISSN
- 1097-0037
- Number of pages
- 18
- Language
- English
- Date published
- 1985
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963113702771
Metrics
1 Record Views