Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Application of Fusion-Fission to the Multi-way Graph Partitioning Problem
verfasst von : Charles-Edmond Bichot
Erschienen in: Parallel Processing and Applied Mathematics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper presents an application of the Fusion-Fission method to the multi-way graph partitioning problem. The Fusion-Fission method was first designed to solve the normalized cut partitioning problem. Its application to the multi-way graph partitioning problem is very recent, thus the Fusion-Fission algorithm has not yet been optimized. Then, the Fusion-Fission algorithm is slower than the state-of-the-art graph partitioning packages. The Fusion-Fission algorithm is compared with JOSTLE, METIS, CHACO and PARTY for four partition’s cardinal numbers: 2, 4, 8 and 16, and three partition balance tolerances: 1.00, 1.01 and 1.03. Results show that up to two thirds of time are the partitions returned by Fusion-Fission of greater quality than those returned by state-of-the-art graph partitioning packages.