Locating median paths on connected outerplanar graphs

In this article, we study the median path problem without length restrictions on the class of connected outerplanar graphs, assuming that weights equal to 1 are assigned to the edges of a graph G, and nonnegative weights are associated to its vertices. We provide an $O(kn)$ time algorithm, where n is the number of vertices of G and k is the number of blocks in G. As a byproduct, when G is a biconnected outerplanar graph, we provide a linear time algorithm to find a median path between two fixed vertices of G without restrictions on the length. In the literature, we did not find polynomial time algorithms for this problem on such classes of graphs. Copyright © 2011 Wiley Periodicals, Inc.