Median problems on wheels and cactus graphs.

This paper is dedicated to location problems on graphs. We propose a linear time algorithm for the 1-median problem on wheel graphs. Moreover, some general results for the 1-median problem are summarized and parametric median problems are investigated. These results lead to a solution method for the 2-median problem on cactus graphs, i.e., on graphs where no two cycles have more than one vertex in common. The time complexity of this algorithm is $$\mathcal O(n^2)$$ , where n is the number of vertices of the graph. [ABSTRACT FROM AUTHOR]