A Note on the Inverse Connected <i>p</i>-Median Problem on Block Graphs

Abstract

Recently, the inverse connected p -median problem on block graphs G ( V , E , w ) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a necessary and sufficient condition for the connected p -median problem on block graphs, developing algorithms and showing that these problems can be solved in O ( n log n ) time, where n is the number of vertices in the underlying block graph. Using similar technique, we show that some results are incorrect by a counter-example. Then we redefine some notations, reprove Theorem 1 and redescribe Theorem 2, Theorem 3 and Theorem 4.