# Graph Partitioning: A Heuristic Procedure to Partition Network Graphs

Das, Pramit and Mishra, Deepak (2009) Graph Partitioning: A Heuristic Procedure to Partition Network Graphs. BTech thesis.

 Preview
PDF
589Kb

## Abstract

Graphs are mathematical structures used to model pair wise relationship between objects of a certain collection. It consists of collection of vertices or “nodes” and a collection of edges that connect these nodes. Graphs can be directed from one vertex to another or undirected. In our context, a graph denotes a network with computers distributed as nodes while the communication channel acting as the edges. These are directed graphs where each edge has a capacity which cannot be exceeded.
In real life applications, it becomes very essential that graphs are partitioned in some way so as to satisfy certain conditions. For example, while placing components of electronic circuit on circuit boards or substrates, components that are highly dependent on each other (exchanging maximum information) should be placed on the same board. Also an important factor is the number of connections between these boards should be minimized. Similar situation arises in a computer network where computer systems are distributed over a wide geographic location. This is the basis of graph partitioning problem.
The classical graph partitioning problem consists of dividing a graph into pieces, such that the pieces are of about same size and there exists very few connections between these pieces. The objective is to partition the nodes of a graph with costs on its edges into subsets so as to minimize the sum of the costs on all edges that are cut.
Let G be graph with n nodes, of sizes (weights) wi > 0, i = 1, 2, …., n. Let p be a positive number, such that 0 < wi < p for all i. Let C = (cij), i,j = 1, 2, ……, n be a weighted connectivity matrix describing the edges of G. Let k be a positive integer. A k-way partition of G is a set of disjoint subsets of G, v1, v2, …, vk such that