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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hendrickson, B., Kolda, T.G.: Partitioning Rectangular and Structurally Nonsymmetric Sparse Matrices for Parallel Processing. SIAM J. Sci. Comput. 21(6), 2048–2072 (2000)
Turhal, B.: Solution of Sparse Linear Systems on a Cluster of Workstations Using Graph Partitioning Methods, Msc. Thesis, Ege University, Int. Computer Institute (2001)
Krishna, P., et al.: A Cluster-based Approach for Routing in Dynamic Networks. ACM SIGCOMM Computer Communication Review 27(2), 49–64 (1997)
Erciyes, K., Marshall, G.: A Cluster based Hierarchical Routing Protocol for Mobile Networks. In: Laganá, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan, C.J.K., Gervasi, O. (eds.) ICCSA 2004. LNCS, vol. 3045, pp. 528–537. Springer, Heidelberg (2004)
Yuanzhu, P.C., Liestman, A.L.: A Zonal Algorithm for Clustering Ad Hoc Networks. Int. J. Foundations of Computer Science 14(2), 305–322 (2003)
Schloegel, K., Karypis, G., Kumar, V.: A New algorithm for Multi-objective Graph Partitioning. Tech. Report 99-003, University of Minnesota, Dept. of CS (1999)
Hendrickson, B., Leland, R., van Driessche, R.: Skewed Graph Partitioning. In: Proc. of 8th SIAM Conf. Parallel Processing for Scientific Computing. SIAM, Philadelphia (1997)
Kernighan, B., Lin, S.: An Effective Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal, 291–308 (1970)
Hendrickson, B., Kolda, T.G.: Graph Partitioning Models for Parallel Computing. Parallel Computing 26, 1519–1534 (2000)
Karypis, G., Kumar, V.: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. Tech. Report 95-035, University of Minnesota, Dept. of CS (1995)
Hendrickson, B., Leland, R.: The Chaco User Guide, V. 2.0. Technical report SAND94- 2692, Sandia National Labs. (1994)
Karypis, G., Kumar, J.: METIS,1.5: A Hypergraph Partitioning package. Tech. Report, Univ. of Minnesota, Dept. of CS (1998)
Pellegrini, F., Roman, J.: SCOTCH: A Software Package for Static Mapping by Dual Recursive Bipartitioning of process and Architecture Graphs. In: Liddell, H., Colbrook, A., Hertzberger, B., Sloot, P.M.A. (eds.) HPCN-Europe 1996. LNCS, vol. 1067, pp. 493–498. Springer, Heidelberg (1996)
Schloegel, K., Karypis, G., Kumar, V.: Graph Partitioning for High Performance Scientific Simulations. Tech. Report 00-018, University of Minnesota, Dept. of CS (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Erciyeş, K., Alp, A., Marshall, G. (2005). Serial and Parallel Multilevel Graph Partitioning Using Fixed Centers. In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds) SOFSEM 2005: Theory and Practice of Computer Science. SOFSEM 2005. Lecture Notes in Computer Science, vol 3381. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30577-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-30577-4_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24302-1
Online ISBN: 978-3-540-30577-4
eBook Packages: Computer ScienceComputer Science (R0)