Sequential and Distributed Algorithms for Fast Graph Partitioning M.A.Sc. Thesis Abstract (c) Shahadat Khan, 1994 Department of ECE University of Victoria In this thesis, we deal with the following k-way graph partitioning (GP) problem: given an undirected weighted graph G(V,E), partition the nodes of G into k parts of almost equal size such that the partition-cost (sum of the weights on edges with nodes in different parts) is minimized. We propose some simple and fast algorithms for this problem for both sequential and distributed computing environments. We give three main algorithms for graph partitioning: direct algorithm AUCTION; and iterative algorithms GPASS and GCYCLE. In the algorithm AUCTION, we introduce the idea of using auction and biddings for the GP problem. This is an inherently distributed algorithm. To the depth of our knowledge this is the first distributed algorithm for this problem. The algorithm GPASS is a greedy iterative algorithm. In each iteration we send a node from the current part to another part in order to get maximum decrease in partition-cost, and iteration can continue taking the destination as the next current part. Our third algorithm GCYCLE is another greedy algorithm where we introduce the idea of cyclic node passing among parts during the iterative improvement stage. In every iteration: at first the parts compute their node passing interests, and then the algorithm finds and processes the cycles of node passing interests. Cyclic node passing is a k-way generalization of the 2-way node exchange found in the Kernighan-Lin approach. We present sequential algorithms for AUCTION, GPASS and GCYCLE, distributed algorithms for AUCTION and GCYCLE, and some of their combinations. We have implemented the sequential algorithms in the Unix environment, and the distributed algorithms in the PVM environment. We compared the experimental performances with Lee's algorithm, and the results show that our algorithms are extremely fast and they produce reasonable quality of solutions.