In this page you will find a copy the files containing the PhD dissertation of Dr. Cid Carvalho de Souza
who is presently working at the Institute of Computing of the State University of Campinas (UNICAMP) in Brazil.
The title of the dissertation is The Graph Equipartition Problem: Optimal Solutions, Extensions and Applications .
It was developed at the Center for Operations Research and Econometrics of the Université Catholique de Louvain
(Louvain-La-Neuve, Belgium) under the supervision of Prof. Dr. Laurence Wolsey.
The dissertation was concluded in November 1993.

Abstract:

In this thesis we study the graph equipartition problem using a polyhedral approach. We derive new classes of valid and facet defining inequalities for the equipartition polytope, namely the Path-Block Cycle and the Suspended Tree inequalities. Exploiting the fact that the equicut polytope is itself a facet of the cut polytope, we have been able to transform the inequalities in these classes to obtain valid and facet defining inequalities for the cut polytope.

The equipartition problem is a special case of the graph partitioning problem with cardinality capacity constraints which, in turn, is a special case of the graph partitioning problem with knapsack capacity constraints. Thus, we have extended the validity of the previous classes of inequalities to these two problems and, for the cardinality case, we have been able to prove that some of them define facets of the polytope. Other different classes of valid inequalities for these more general problems are introduced.

We report the computational results we have obtained with a branch-and-cut code based upon the insertion of these valid inequalities to the linear relaxation of graph partition problems with knapsack capacity constraints. The test problems come from mesh partition in Finite Elements, compiler design and VLSI design.

In addition, we propose a new heuristic algorithm for the problem of minimizing the frontwidth of a finite element mesh. This heuristic is based on a divide-and-conquer strategy that recursively solves graph equipartition problems. Different variants of this heuristic are tested for a small sample of 2D and 3D meshes and the results are compared to those obtained by the classical Cuthill-McKee algorithm. From our tests, we conclude that our approach is quite effective in generating element orderings with small frontwidths.

Files:

For technical reasons some of the tables and figures of Chapters 4 e 5 could not be retrieved and included in the full version of the text. They have been reproduced independently and can also be downloaded if necessary.

The list of files available is the following:


Last updated at 15/02/2001 by cid