Skip navigation

Mesh partitioning: A multilevel balancing and refinement algorithm

Mesh partitioning: A multilevel balancing and refinement algorithm

Walshaw, Christopher ORCID: 0000-0003-0253-7779 and Cross, Mark (1998) Mesh partitioning: A multilevel balancing and refinement algorithm. Other. CMS Press, London, UK.

Full text not available from this repository.


Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan-Lin partition optimisation algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of the-art partitioner and shown to provide improved results.

Item Type: Monograph (Other)
Additional Information: This paper was later published in SIAM Journal on Scientific Computing, 22 (1). pp. 63-80, 2000; also available from this repository. Mathematics Research Report 98/IM/35 ISBN: 978-1899991358
Uncontrolled Keywords: graph-partitioning, mesh partitioning, load-balancing, multilevel algorithms
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments: School of Computing & Mathematical Sciences
Last Modified: 14 Oct 2016 08:59

Actions (login required)

View Item View Item