Block‐vertex duality and the one‐median problem

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).