Premium
Locating median paths on connected outerplanar graphs
Author(s) -
Lari Isabella,
Ricca Federica,
Scozzari Andrea,
Becker Ronald I.
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20426
Subject(s) - combinatorics , mathematics , time complexity , graph , path (computing) , discrete mathematics , computer science , programming language
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. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011