Soper, A. J. ORCID: 0000-0002-0901-9803, Walshaw, C. ORCID: 0000-0003-0253-7779 and Cross, M. (2004) A combined evolutionary search and multilevel optimisation approach to graph-partitioning. Journal of Global Optimization, 29 (2). pp. 225-241. ISSN 0925-5001 (Print), 1573-2916 (Online) (doi:https://doi.org/10.1023/B:JOGO.0000042115.44455.f3)

Full text not available from this repository.

Abstract

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Item Type:	Article
Additional Information:	[1] Copyright: © 2004 Kluwer Academic Publishers. Printed in the Netherlands.
Uncontrolled Keywords:	evolutionary search, genetic algorithms, graph-partitioning, multilevel optimisation
Subjects:	Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group:	Faculty of Liberal Arts & Sciences
Related URLs:	Publisher Publisher
Last Modified:	14 Oct 2016 09:02
URI:	http://gala.gre.ac.uk/id/eprint/815

Actions (login required)

View Item