Tech Report CS-93-47

A Data Structure for Bicategories with Application to Speeding Up an Approximation Algorithm

Abstract:

We introduce a data-structure problem on graphs we call the bicategory problem, and a data structure that solves it in $O(\sqrt m \log m)$ time, where m is the number of edges. We show how this data structure can be used in quickly computing approximately minimum-cost networks. The resulting time bound for the approximation algorithm is $O(n \sqrt m \log m)$ where n and m are the number of nodes and edges in the input graph, an improvement over the previously known bound of $O(n^2 \sqrt{\log \log n})$ when the input graph is sparse.

(complete text in pdf or gzipped postscript)