On the partitioning of graphs and hypergraphs
Mallek Khellaf, Dorit S. Hochbaum, Ilan Adler · 1987
We study, in the first part of this thesis, the combinatorial problem that consists of partitioning the nodes of a weighted graph into bounded size disjoint clusters such that the sum of the weights of the edges whose end vertices belong to the same cluster is maximum. The complexity of the problem is put into perspective with other graph partitioning problems. We present a class of approximation algorithms, based on matching, for the problem of partitioning the nodes of a graph into equally sized subsets. These approximation algorithms are analyzed and shown to yield practical worst case bounds. Numerical experiments with the heuristics and exact solution procedures on real-world and random problems are reported. In the second part of this thesis, we address the problem of allocating the relations of a database to the sites of a computer network. A general model of the problem is presented and linked to hypergraph partitioning. An optimization algorithm based on two lower bounding schemes is described. Successful computational experiments are also reported.