Some fast algorithms on graphs and trees
Heather Booth · 1991
Presented here are three fast algorithms solving problems concerning trees or graphs. We give a linear-time algorithm for finding a balanced decomposition of a k-ary tree where k is a constant not related to the input size. A different linear-time algorithm for finding a balanced decomposition of a binary tree was discovered previously by Guibas, Leven, Hershberger, Sharir, and Tarjan (26). We also consider the problem of finding a minimum-cost maximum flow in a series-parallel network. The algorithm presented here runs in $O(m$ log $m$) time on an m-edge series-parallel network and requires $O(m$ log log $m$) space. This is an improvement over the algorithm presented by Bein, Brucker, and Tamir (6), which runs in $O(m$ log $m + mn)$ time, where $n$ is the number of vertices. In an effort to improve the space requirement we also present an algorithm which uses $O(m)$ space but runs in $O(m$ log $m$ log log $m$) time. Finally, we consider the problem of finding all replacement edges for a minimum spanning tree of a planar graph. We present an algorithm for solving this problem which runs in linear time. This algorithm also performs sensitivity analysis for the minimum spanning tree, shortest path, and network flow problems. The first two algorithms presented rely on the use of balanced binary trees for efficient representation of data. We give an overview of the relevant red-black tree and finger tree techniques in introductory chapter.