Please use this identifier to cite or link to this item: https://hdl.handle.net/11147/1982
Title: Serial and parallel multilevel graph partitioning using fixed centers
Authors: Erciyeş, Kayhan
Alp, Ali
Marshall, Geoffrey
Erciyeş, Kayhan
Keywords: Algorithms
Costs
Graph theory
Partitioning
Parallel algorithm
Issue Date: 2005
Publisher: Springer Verlag
Source: Erciyeş, K., Alp, A., and Marshall, G. (2005). Serial and parallel multilevel graph partitioning using fixed centers. Lecture Notes in Computer Science, 3381, 127-136. doi:10.1007/978-3-540-30577-4_16
Abstract: We present new serial and parallel algorithms for multilevel graph partitioning. Our algorithm has coarsening, partitioning and uncoarsening phases like other multilevel partitioning methods. However, we choose fixed nodes which are at least a specified distance away from each other and coarsen them with their neighbor nodes in the coarsening phase using various heuristics. Using this algorithm, it is possible to obtain theoretically and experimentally much more balanced partitions with substantially decreased total edge costs between the partitions than other algorithms. We also developed a parallel method for the fixed centered partitioning algorithm. It is shown that parallel fixed centered partitioning obtains significant speedups compared to the serial case.
Description: 31st Conference on Current Trends in Theory and Practice of Computer Science; Liptovsky Jan; Slovakia; 22 January 2005 through 28 January 2005
URI: http://doi.org/10.1007/978-3-540-30577-4_16
http://hdl.handle.net/11147/1982
ISSN: 0302-9743
0302-9743
1611-3349
Appears in Collections:Computer Engineering / Bilgisayar Mühendisliği
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Files in This Item:
File Description SizeFormat 
1982.pdfConference Paper166.53 kBAdobe PDFThumbnail
View/Open
Show full item record

CORE Recommender

Google ScholarTM

Check

Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.