×
Safro, Ilya; Sanders, Peter; Schulz, Christian

Advanced coarsening schemes for graph partitioning. (English) Zbl 1347.68355

ACM J. Exp. Algorithm. 19, Spec. Iss. 1, Article No. 2.2, 24 p. (2014).

Cited in 15 Documents

MSC:

68W05 Nonnumerical algorithms
05C12 Distance in graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68W40 Analysis of algorithms

Keywords:

coarsening; algebraic distance; computational optimization; multilevel algorithm; refinement; uncoarsening

Software:

DibaP; SNAP; Bubble-FOS/C; KaHIP; JOSTLE; KaFFPa; DIMACS
Cite Review PDF
Full Text: DOI arXiv

References:

[1] D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner. 2013. 10th DIMACS Implementation Challenge—Graph Partitioning and Graph Clustering. Retrieved October 20, 2014, from http://www.cc.gatech.edu/dimacs10/. · Zbl 1262.05001
[2] G. Bartel, C. Gutwenger, K. Klein, and P. Mutzel. 2010. An experimental evaluation of multilevel layout methods. In Graph Drawing. Lecture Notes in Computer Science, Vol. 6502. Springer, 80-91. · Zbl 1314.68217
[3] A. Brandt. 2001. Multiscale scientific computation: Review 2001. In Multiscale and Multiresolution Methods. Lecture Notes in Computational Science and Engineering, Vol. 20. Springer, 3-95. · Zbl 0989.65140
[4] A. Brandt and D. Ron. 2003. Multigrid solvers and multilevel optimization strategies. In Multilevel Optimization in VLSICAD. Combinatorial Optimization, Vol. 14. Springer, 1-69. · Zbl 1046.65043
[5] T. N. Bui and C. Jones. 1992. Finding good approximate vertex and edge partitions is NP-hard. Information Processing Letters 42, 3, 153-159. · Zbl 0764.68061
[6] T. N. Bui and B. R. Moon. 1996. Genetic algorithm and graph partitioning. IEEE Transactions on Computers 45, 7, 841-855. DOI: http://dx.doi.org/10.1109/12.508322 · Zbl 1049.68605
[7] J. Chen and I. Safro. 2011. Algebraic distance on graphs. SIAM Journal on Scientific Computing 33, 6, 3468-3490. · Zbl 1235.05042
[8] C. Chevalier and I. Safro. 2009. Comparison of coarsening schemes for multilevel graph partitioning. In LION. Lecture Notes in Computer Science, Vol. 5851. Springer, 191-205.
[9] I. Dhillon. 2005. A fast kernel-based multilevel algorithm for graph clustering. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 629-634.
[10] D. Drake and S. Hougardy. 2003. A simple approximation algorithm for the weighted matching problem. Information Processing Letters 85, 211-213. · Zbl 1173.68861
[11] N. Fan and P. M. Pardalos. 2010. Linear and quadratic programming approaches for the general graph partitioning problem. Journal of Global Optimization 48, 1, 57-71. DOI: http://dx.doi.org/10.1007/s10898-009-9520-1 · Zbl 1202.90261
[12] C. M. Fiduccia and R. M. Mattheyses. 1982. A linear-time heuristic for improving network partitions. In Proceedings of the 19th Conference on Design Automation. 175-181.
[13] P. O. Fjallstrom. 1998. Algorithms for graph partitioning: A survey. Linkoping Electronic Articles in Computer and Information Science 3, 10.
[14] W. W. Hager and Y. Krylyuk. 1999. Graph partitioning and continuous quadratic programming. SIAM Journal on Discrete Mathematics 12, 4, 500-523. · Zbl 0972.90086
[15] W. W. Hager, D. T. Phan, and H. Zhang. 2013. An exact algorithm for graph partitioning. Mathematical Programming 137, 1-2, 531-556. · Zbl 1263.90115
[16] M. T. Heath. 2002. Scientific Computing: An Introductory Survey. McGraw-Hill. http://books.google.com/books?id=DPkYAQAAIAAJ. · Zbl 1411.65003
[17] M. Holtgrewe, P. Sanders, and C. Schulz. 2010. Engineering a scalable high quality graph partitioner. In Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing. 1-10.
[18] Y. F. Hu and J. A. Scott. 2001. A multilevel algorithm for wavefront reduction. SIAM Journal on Scientific Computing 23, 4, 1352-1375. DOI: http://dx.doi.org/10.1137/S1064827500377733 · Zbl 0999.65022
[19] S. E. Karisch, F. Rendl, and J. Clausen. 2000. Solving graph bisection problems with semidefinite programming. INFORMS Journal on Computing 12, 3, 177-191. DOI: http://dx.doi.org/10.1287/ijoc.12.3. 177.12637 · Zbl 1040.90045
[20] G. Karypis and V. Kumar. 1995. Analysis of multilevel graph partitioning. In Proceedings of the 1995 ACM/IEEE Conference on Supercomputing (Supercomputing’95). Article No. 29.
[21] J. Lescovec. n.d. Stanford Network Analysis Package (SNAP). Retrieved October 20, 2014, from http://snap.stanford.edu/index.html.
[22] J. Maue and P. Sanders. 2007. Engineering algorithms for approximate weighted matching. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 4525. Springer, 242-255. http://dx.doi.org/10.1007/978-3-540-72845-0_19 · Zbl 1203.68317
[23] H. Meyerhenke, B. Monien, and T. Sauerwald. 2008. A new diffusion-based multilevel algorithm for computing graph partitions of very high quality. In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS’08). 1-13.
[24] F. Pellegrini. Scotch Home Page. n.d. Retrieved October 20, 2014, from http://www.labri/fr/perso/pelegrin/scotch/.
[25] A. Pothen, H. D. Simon, and K.-P. Liou. 1990. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Matrix Analalysis and Applications 11, 3, 430-452. DOI: http://dx.doi.org/10.1137/0611030 · Zbl 0711.65034
[26] D. Ron, I. Safro, and A. Brandt. 2011. Relaxation-based coarsening and multiscale graph organization. Multiscale Modeling & Simulation 9, 1, 407-423. · Zbl 1219.68125
[27] D. Ron, S. Wishko-Stern, and A. Brandt. 2005. An Algebraic Multigrid Based Algorithm for Bisectioning General Graphs. Technical Report MCS05-01. Department of Computer Science and Applied Mathematics, Weizmann Institute of Science.
[28] I. Safro, D. Ron, and A. Brandt. 2006. Graph minimum linear arrangement by multilevel weighted edge contractions. Journal of Algorithms 60, 1, 24-41. · Zbl 1096.68687
[29] I. Safro, D. Ron, and A. Brandt. 2008. Multilevel algorithms for linear ordering problems. Journal of Experimental Algorithmics 13, 1.4-1.20. · Zbl 1284.68685
[30] I. Safro, P. Sanders, and C. Schulz. n.d. Benchmark with Potentially Hard Graphs for Partitioning Problem. Retrieved October 20, 2014, from http://www.cs.clemson.edu/∼isafro/hardpart.html. · Zbl 1347.68355
[31] P. Sanders and C. Schulz. 2011. Engineering multilevel graph partitioning algorithms. In Algorithms—ESA 2011. Lecture Notes in Computer Science, Vol. 6942. Springer, 469-480. · Zbl 1346.05288
[32] P. Sanders and C. Schulz. 2012. Distributed evolutionary graph partitioning. In Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation (ALENEX’12). 16-29. · Zbl 1430.68237
[33] K. Schloegel, G. Karypis, V. Kumar, J. Dongarra, I. Foster, G. Fox, K. Kennedy, and A. White. 2000. Graph Partitioning for High Performance Scientific Simulations. Morgan Kaufmann.
[34] E. Sharon, A. Brandt, and R. Basri. 2000. Fast multiscale image segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 70-77. citeseer.nj.nec.com/sharon99fast.html.
[35] A. J. Soper, C. Walshaw, and M. Cross. 2004. A combined evolutionary search and multilevel optimisation approach to graph-partitioning. Journal of Global Optimization 29, 2, 225-241. · Zbl 1084.90049
[36] L. E. Stock. 2006. Strategic Logistics Management. Lightning Source, La Vergne, TN. http://books.google.com/books?id=1LyCAQAACAAJ.
[37] L. Tang, H. Liu, J. Zhang, and Z. Nazeri. 2008. Community evolution in dynamic multi-mode networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’08). 677-685.
[38] U. Trottenberg and A. Schuller. 2001. Multigrid. Academic Press, Orlando, FL. · Zbl 0976.65106
[39] C. Walshaw. 2004. Multilevel refinement for combinatorial optimisation problems. Annals of Operations Research 131, 1, 325-372. · Zbl 1067.90145
[40] C. Walshaw and M. Cross. 2007. JOSTLE: Parallel multilevel graph-partitioning software—an overview. In Mesh Partitioning Techniques and Domain Decomposition Techniques, F. Magoules (Ed.). Civil-Comp Ltd., 27-58.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.