Premium
Block‐vertex duality and the one‐median problem
Author(s) -
Chen M.L.,
Francis R. L.,
Lawrence J. F.,
Lowe T. J.,
Tufekci S.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150402
Subject(s) - combinatorics , mathematics , block (permutation group theory) , graph , vertex (graph theory) , discrete mathematics
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).