Some Fast Algorithms on Graphs and Trees (thesis)

Abstract:

Presented 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 imput 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. We also consider the problem of finding a minimum-cost maximum flow in a series-parallel network. The algorithm presented here runs in O(mlog logm) time on an m-edge series-parallel network and requires O(mlog logm) space. This is an
improvement over the algorithm presented by Bein, Brucker and Tamir, which runs in O(mlogm+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(mlogmlog logm) 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.