NobleBlocks

Research indexJournal article

Fractal Graph Optimization Algorithms

Riehl, Hespanha

4 Oct 2006

NobleIDark:/48914/w1/20260516/5A817D41DOI10.1109/cdc.2005.1582486

Paywalled

The full text is at the publisher

You can read the abstract here, or open it at the publisher.

Read at the publisher

Abstract

We introduce methods of hierarchically decomposing three types of graph optimization problems: all-pairs shortest path, all-pairs maximum flow,and search. Each method uses a partition on the graph to create a high level problem and several lower level problems. The computations on each level are identical, so the low level problems can be further decomposed. In this way, the problems become fractal in nature. We use these decomposition methods to establish upper and lower bounds on the optimal criteria of each problem, which can be achieved with much less computation than what is required to solve the original problem. Also, for each problem, we find an optimal number of partitions that minimizes computation time. As the number of hierarchical levels increases, the computational complexity decreases at the expense of looser bounds.

Discussion

Citations

Topics

More

Suggest a correction or report