Block-vertex duality and the one-median problem

✍ Scribed by M.-L. Chen; R. L. Francis; J. F. Lawrence; T. J. Lowe; S. Tufekci

• Publisher: John Wiley and Sons
• Year: 1985
• Tongue: English
• Weight: 854 KB
• Volume: 15
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230150402

✦ Synopsis

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 ( 8 ) 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(lV1) algorithm to solve the two problems on C, and we characterize the solutions. We also show that the solution to a 1-median problem defined on C 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).