A linear algorithm for the pos/neg-weighted 1-median problem on a cactus

The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos/neg-weighted’ problem defined on a cactus. The algorithm visits every vertex just once and runs thus in linear time.