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 O(n(2)), where n is the number of vertices of the graph.
median problem cactus graphs location problem wheel graphs