{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T20:50:15Z","timestamp":1761252615904},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642111686"},{"type":"electronic","value":"9783642111693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11169-3_14","type":"book-chapter","created":{"date-parts":[[2009,11,27]],"date-time":"2009-11-27T21:26:05Z","timestamp":1259357165000},"page":"191-205","source":"Crossref","is-referenced-by-count":42,"title":["Comparison of Coarsening Schemes for Multilevel Graph Partitioning"],"prefix":"10.1007","author":[{"given":"C\u00e9dric","family":"Chevalier","sequence":"first","affiliation":[]},{"given":"Ilya","family":"Safro","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoretical Computer Science\u00a01, 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"14_CR2","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A. Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Analysis\u00a011(3), 430\u2013452 (1990)","journal-title":"SIAM Journal of Matrix Analysis"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. BELL System Technical Journal, 291\u2013307 (1970)","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"14_CR4","first-page":"175","volume-title":"Proceedings of the 19th Design Automation Conference","author":"C.M. Fiduccia","year":"1982","unstructured":"Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: Proceedings of the 19th Design Automation Conference, pp. 175\u2013181. IEEE, Los Alamitos (1982)"},{"issue":"7","key":"14_CR5","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1109\/12.508322","volume":"45","author":"T.N. Bui","year":"1996","unstructured":"Bui, T.N., Moon, B.R.: Genetic algorithm and graph partitioning. IEEE Trans. Comput.\u00a045(7), 841\u2013855 (1996)","journal-title":"IEEE Trans. Comput."},{"key":"14_CR6","volume-title":"Multilevel Optimization and VLSICAD","author":"A. Brandt","year":"2003","unstructured":"Brandt, A., Ron, D.: Ch. 1: Multigrid solvers and multilevel optimization strategies. In: Cong, J., Shinnerl, J.R. (eds.) Multilevel Optimization and VLSICAD. Kluwer, Dordrecht (2003)"},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1023\/B:ANOR.0000039525.80601.15","volume":"131","author":"C. Walshaw","year":"2004","unstructured":"Walshaw, C.: Multilevel refinement for combinatorial optimisation problems. Annals Oper. Res.\u00a0131, 325\u2013372 (2004)","journal-title":"Annals Oper. Res."},{"key":"14_CR8","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1145\/1055137.1055185","volume-title":"ISPD","author":"T.F. Chan","year":"2005","unstructured":"Chan, T.F., Cong, J., Romesis, M., Shinnerl, J.R., Sze, K., Xie, M.: mpl6: a robust multilevel mixed-size placement engine. In: Groeneveld, P., Scheffer, L. (eds.) ISPD, pp. 227\u2013229. ACM, New York (2005)"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1109\/TCAD.2003.809661","volume":"22","author":"C. Chang","year":"2003","unstructured":"Chang, C., Cong, J., Pan, D., Yuan, X.: Multilevel global placement with congestion control. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems\u00a022, 395\u2013409 (2003)","journal-title":"IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems"},{"volume-title":"Multilevel Optimization and VLSICAD","year":"2003","key":"14_CR10","unstructured":"Cong, J., Shinnerl, J.R. (eds.): Multilevel Optimization and VLSICAD. Kluwer, Dordrecht (2003)"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Safro, I., Ron, D., Brandt, A.: Multilevel algorithms for linear ordering problems. Journal of Experimental Algorithmics\u00a013, 1.4\u20131.20 (2008)","DOI":"10.1145\/1412228.1412232"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Abou-Rjeili, A., Karypis, G.: Multilevel algorithms for partitioning power-law graphs. In: IPDPS (2006)","DOI":"10.21236\/ADA439402"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Alpert, C.J., Huang, J.H., Kahng, A.B.: Multilevel circuit partitioning. In: Design Automation Conference, pp. 530\u2013533 (1997)","DOI":"10.1145\/266021.266275"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-36605-9_14","volume-title":"Applications of Evolutionary Computing","author":"R. Banos","year":"2003","unstructured":"Banos, R., Gil, C., Ortega, J., Montoya, F.: Multilevel heuristic algorithm for graph partitioning. In: Raidl, G.R., Cagnoni, S., Cardalda, J.J.R., Corne, D.W., Gottlieb, J., Guillot, A., Hart, E., Johnson, C.G., Marchiori, E., Meyer, J.-A., Middendorf, M. (eds.) EvoIASP 2003, EvoWorkshops 2003, EvoSTIM 2003, EvoROB\/EvoRobot 2003, EvoCOP 2003, EvoBIO 2003, and EvoMUSART 2003. LNCS, vol.\u00a02611, pp. 143\u2013153. Springer, Heidelberg (2003)"},{"key":"14_CR15","unstructured":"Ron, D., Wishko-Stern, S., Brandt, A.: An algebraic multigrid based algorithm for bisectioning general graphs. Technical Report MCS05-01, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science (2005)"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1002\/cpe.4330060203","volume":"6","author":"S.T. Barnard","year":"1994","unstructured":"Barnard, S.T., Simon, H.D.: A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience\u00a06, 101\u2013107 (1994)","journal-title":"Concurrency: Practice and Experience"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., Leland, R.W.: A multi-level algorithm for partitioning graphs. In: Supercomputing (1995)","DOI":"10.1145\/224170.224228"},{"key":"14_CR18","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. Technical Report 95-035, University of Minnesota (1995)"},{"key":"14_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BFb0030098","volume-title":"Parallel Algorithms for Irregularly Structured Problems","author":"U. Catalyurek","year":"1996","unstructured":"Catalyurek, U., Aykanat, C.: Decomposing irregularly sparse matrices for parallel matrix-vector multiplications. In: Saad, Y., Yang, T., Ferreira, A., Rolim, J.D.P. (eds.) IRREGULAR 1996. LNCS, vol.\u00a01117, pp. 75\u201386. Springer, Heidelberg (1996)"},{"issue":"2","key":"14_CR20","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1109\/5992.988653","volume":"4","author":"K. Devine","year":"2002","unstructured":"Devine, K., Boman, E., Heaphy, R., Hendrickson, B., Vaughan, C.: Zoltan data management services for parallel dynamic applications. Computing in Science and Engineering\u00a04(2), 90\u201397 (2002)","journal-title":"Computing in Science and Engineering"},{"key":"14_CR21","unstructured":"Walshaw, C.: A multilevel approach to the travelling salesman problem. Tech. Rep. 00\/IM\/63, Comp. Math. Sci., Univ. Greenwich, London SE10 9LS, UK (2000)"},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"2000","DOI":"10.1137\/S1064827500377733","volume":"23","author":"Y.F. Hu","year":"2001","unstructured":"Hu, Y.F., Scott, J.A.: A multilevel algorithm for wavefront reduction. SIAM J. Scientific Computing\u00a023, 2000\u20132031 (2001)","journal-title":"SIAM J. Scientific Computing"},{"key":"14_CR23","volume-title":"Proc. 22nd International Parallel and Distributed Processing Symposium, (IPDPS 2008)","author":"H. Meyerhenke","year":"2008","unstructured":"Meyerhenke, H., Monien, B., Sauerwald, T.: A new diffusion-based multilevel algorithm for computing graph partitions of very high quality. In: Proc. 22nd International Parallel and Distributed Processing Symposium (IPDPS 2008). IEEE Computer Society, Los Alamitos (2008); Best Algorithms Paper Award"},{"key":"14_CR24","unstructured":"scotch: Static mapping, graph partitioning, and sparse matrix block ordering package, http:\/\/www.labri.fr\/~pelegrin\/scotch\/"},{"key":"14_CR25","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1137\/S1064827593255135","volume":"18","author":"H.D. Simon","year":"1997","unstructured":"Simon, H.D., Teng, S.H.: How good is recursive bisection. SIAM J. Sci. Comput.\u00a018, 1436\u20131445 (1997)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2000","key":"14_CR26","first-page":"1","volume":"10","author":"A. Brandt","year":"2000","unstructured":"Brandt, A.: General highly accurate algebraic coarsening. Electronic Trans. Num. Anal.\u00a010(2000), 1\u201320 (2000)","journal-title":"Electronic Trans. Num. Anal."},{"issue":"1","key":"14_CR27","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.jalgor.2004.10.004","volume":"60","author":"I. Safro","year":"2006","unstructured":"Safro, I., Ron, D., Brandt, A.: Graph minimum linear arrangement by multilevel weighted edge contractions. Journal of Algorithms\u00a060(1), 24\u201341 (2006)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"14_CR28","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/S0895480199335829","volume":"12","author":"W.W. Hager","year":"1999","unstructured":"Hager, W.W., Krylyuk, Y.: Graph partitioning and continuous quadratic programming. SIAM J. Discret. Math.\u00a012(4), 500\u2013523 (1999)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"14_CR29","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0168-9274(01)00115-5","volume":"41","author":"V.E. Henson","year":"2002","unstructured":"Henson, V.E., Yang, U.M.: Boomeramg: a parallel algebraic multigrid solver and preconditioner. Appl. Numer. Math.\u00a041(1), 155\u2013177 (2002)","journal-title":"Appl. Numer. Math."},{"key":"14_CR30","unstructured":"Gee, M., Siefert, C., Hu, J., Tuminaro, R., Sala, M.: ML 5.0 smoothed aggregation user\u2019s guide. Technical Report SAND2006-2649, Sandia National Laboratories (2006)"},{"key":"14_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/11823285_25","volume-title":"Euro-Par 2006 Parallel Processing","author":"C. Chevalier","year":"2006","unstructured":"Chevalier, C., Pellegrini, F.: Improvement of the efficiency of genetic algorithms for scalable parallel graph partitioning in a multi-level framework. In: Nagel, W.E., Walter, W.V., Lehner, W. (eds.) Euro-Par 2006. LNCS, vol.\u00a04128, pp. 243\u2013252. Springer, Heidelberg (2006)"},{"issue":"6-8","key":"14_CR32","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.parco.2007.12.001","volume":"34","author":"C. Chevalier","year":"2008","unstructured":"Chevalier, C., Pellegrini, F.: Pt-scotch: A tool for efficient parallel graph ordering. Parallel Comput.\u00a034(6-8), 318\u2013331 (2008)","journal-title":"Parallel Comput."}],"container-title":["Lecture Notes in Computer Science","Learning and Intelligent Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11169-3_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T17:47:21Z","timestamp":1685209641000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11169-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642111686","9783642111693"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11169-3_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}