Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
ISSN 1759-3158
Edited by: F. Magoulès
Chapter 1

Graph and Mesh Partitioning: An Overview of the Current State-of-the-Art

R. Baños Navarro and C. Gil Montoya

Department of Computer Architecture and Electronics, University of Almeria, Spain

Full Bibliographic Reference for this chapter
R. Baños Navarro, C. Gil Montoya, "Graph and Mesh Partitioning: An Overview of the Current State-of-the-Art", in F. Magoulès, (Editor), "Mesh Partitioning Techniques and Domain Decomposition Methods", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 1, pp 1-26, 2007. doi:10.4203/csets.17.1
Keywords: mesh partitioning, graph partitioning, load balancing, domain decomposition, VLSI design, heuristic methods, multi-constraint optimisation, multi-objective optimisation.

Efficient partitioning methods are critical for developing efficient solutions in a large variety of applications. For example, large-scale scientific simulations on parallel computers require the allocation of finite element meshes among the processors such that the number of elements assigned to each processor and the number of contiguous elements assigned to different processors is as low as possible. Graph partitioning algorithms can be used to satisfy these conditions by first modelling the mesh with a graph, and then partitioning it into several sub-graphs which represent mesh decomposition. This study provides a description of this problem and the current state of the art in mesh and graph partitioning methods, including multi-constraint and multi-objective approaches. It also offers information on several public domain packages for graph and mesh partitioning.

purchase the full-text of this chapter (price £25)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)