Back to results

University of Victoria (Canada)

Sequential and distributed algorithms for fast graph partitioning

Abstract

dc:description.abstract

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 AUC­TION; and iterative algorithms GREEDYPASS and GREEDYCYCLE. In the al­gorithm 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 algo­rithm GREEDYPASS 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 GREEDYCYCLE is another greedy algorithm where we introduce the idea of cyclic node passing among parts during the it­erative 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, GREEDY PASS and GREEDY­CYCLE, distributed algorithms for AUCTION and GREEDYCYCLE, and some of their combinations. We have implemented the sequential algorithms in the Unix environment, and the distributed algorithms in the PYM environment. We com­pared the experimental performances with Lee's algorithm, and the results show that our algorithms are extremely fast and they produce reasonable quality of solutions.

Degree

thesis:*
Level thesis:degree_level
Master of Applied Science M.A.Sc.
Department thesis:degree_department
Department of Electrical and Computer Engineering
Year dc:date.issued
1994

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Khan, Md. Shahadatullah

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1828/18466

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Khan, Md. Shahadatullah. Sequential and distributed algorithms for fast graph partitioning. Master of Applied Science M.A.Sc. thesis, 1994. https://hdl.handle.net/1828/18466