Efficient Graph Algorithms for Sequential and Parallel Computers.
Abstract
This thesis studies graph algorithms, both in sequential and parallel contexts. In the following outline of the thesis, algorithm complexities are stated in terms of the the number of vertices n, the number of edges m, the largest absolute value of capacities U, and the largest absolute value of costs C. Chapter 1 introduces a new approach to the maximum flow problem that leads to better algorithms for the problem. Chapter 2 is devoted to the minimum cost flow problem, which is a generalization of the maximum flow problem. Chapter 3 addresses implementation of parallel algorithms through a case-study of an implementation of a parallel maximum flow algorithm. Parallel prefix operations play an important role in our implementation. Present experimental results achieved by the implementation are presented. Present Parallel symmetry-breaking techniques are the main topic of Chapter 4. Keywords: network flows; parallel algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1987
- Accession Number
- ADA178403
Entities
People
- Andrew V. Goldberg
Organizations
- Massachusetts Institute of Technology