Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
Refael Hassin, Arie Tamir · SIAM Journal on Algebraic and Discrete Methods · 1986
It is well known that a series-parallel multigraph G can be constructed recursively from its edges. This construction is represented by a binary decomposition tree. This is a rooted binary tree T in which each vertex q corresponds to some series-parallel submultigraph of G, denoted by $G ( q )$, obtained as follows. Each leaf (tip) of T represents a distinct edge of G. If q is not a leaf then it is either of a series or parallel type. If $q_1 $ and $q_2 $ are the two sons of q on T, $G ( q )$ is the submultigraph obtained from $G ( q_1 )$ and $G ( q_2 )$ by the respective series or parallel composition. In this paper we use this tree to develop efficient algorithms for several optimization and selection problems defined on graphs with no $K_4 $ homeomorph. In particular, we provide a linear time algorithm to find the shortest simple paths from a given vertex to all other vertices. We also construct an $O ( n^4 )$ algorithm to solve the uncapacitated plant location problem, where n is the number of vertices. We prove that graphs with no $K_4 $ homeomorph contain a 2-separator, and then use it to show that the kth longest path in the set of all intervertex distances can be selected in $O ( n\log ^3 n )$ time.