{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T14:36:20Z","timestamp":1768401380972,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2016,1,29]],"date-time":"2016-01-29T00:00:00Z","timestamp":1454025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Research Foundation (DFG) grant Towards Exascale Application Mapping\u2014An Algorithmic Framework for Load Balancing on Non-Uniform, Massively Parallel Machines"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2016,11,4]]},"abstract":"<jats:p>A hierarchy of increasingly coarse versions of a network allows one to represent the network on multiple scales at the same time. Often, the elementary operation for generating a hierarchy on a network is merging adjacent vertices, an operation that can be realized through contracting the edge between the two vertices. Such a hierarchy is defined by the selection of the edges to be contracted between a level and the next coarser level. The selection may involve (i) rating the edges, (ii) constraining the selection (e.g., that the selected edges form a matching), as well as (iii) maximizing the total rate of the selected edges under the constraints. Hierarchies of this kind are, among others, involved in multilevel methods for partitioning networks\u2014a prerequisite for processing in parallel with distributed memory.<\/jats:p>\n          <jats:p>In this article, we propose a new edge rating by (i) defining weights for the edges of a network that express the edges\u2019 importance for connectivity via shortest paths, (ii) computing a minimum weight spanning tree with respect to these weights, and (iii) rating the network edges based on the conductance values of the tree\u2019s fundamental cuts.<\/jats:p>\n          <jats:p>\n            To make the computation of our new edge rating efficient, we develop the first optimal linear-time algorithm to compute the conductance values of\n            <jats:italic>all<\/jats:italic>\n            fundamental cuts of a given spanning tree. We integrate the new edge rating into a leading multilevel graph partitioner and equip the latter also with a new greedy postprocessing for optimizing the Maximum Communication Volume (MCV) of a partition.\n          <\/jats:p>\n          <jats:p>Our experiments, in which we bipartition frequently used benchmark networks, show that the postprocessing reduces MCV by 11.3%. Our new edge rating, here used for matching-based coarsening, further reduces MCV by 10.3% compared to the previously best rating with MCV postprocessing in place for both ratings. In total, with a modest increase in running time, our new approach reduces the MCV of complex network partitions by 20.4%.<\/jats:p>","DOI":"10.1145\/2851496","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T20:37:54Z","timestamp":1454359074000},"page":"1-20","source":"Crossref","is-referenced-by-count":6,"title":["Tree-Based Coarsening and Partitioning of Complex Networks"],"prefix":"10.1145","volume":"21","author":[{"given":"Roland","family":"Glantz","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany"}]},{"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany"}]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2016,1,29]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Challenge. Contemporary Mathematics","volume":"588","author":"Bader D.","year":"2013"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690192"},{"key":"e_1_2_2_3_1","unstructured":"C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley.  C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley."},{"key":"e_1_2_2_4_1","volume-title":"6th SIAM Conference on Parallel Processing for Scientific Computing (PPSC). 445--452","author":"Bui T. N."},{"key":"e_1_2_2_5_1","unstructured":"A. Bulu\u00e7 H. Meyerhenke I. Safro P. Sanders and C. Schulz. 2014. Recent Advances in Graph Partitioning. Technical Report arXiv:1311.3144.  A. Bulu\u00e7 H. Meyerhenke I. Safro P. Sanders and C. Schulz. 2014. Recent Advances in Graph Partitioning. Technical Report arXiv:1311.3144."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775087"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11169-3_14"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2011.572452"},{"key":"e_1_2_2_9_1","volume-title":"Graduate Texts in Mathematics","volume":"173","author":"Diestel R.","year":"2012"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"B. Fagginger Auer and R. Bisseling. 2013. Graph coarsening and clustering on the GPU. In Graph Partitioning and Graph Clustering. AMS and DIMACS.  B. Fagginger Auer and R. Bisseling. 2013. Graph coarsening and clustering on the GPU. In Graph Partitioning and Graph Clustering. AMS and DIMACS.","DOI":"10.1090\/conm\/588\/11706"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000022288.19776.77"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_5"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_31"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.57"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the DAGM Symposium","volume":"2449","author":"Haxhimusa Y.","year":"2002"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224228"},{"key":"e_1_2_2_20_1","volume-title":"24th International Parallel and Distributed Processing Symposium (IPDPS).","author":"Holtgrewe M."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_2_22_1","volume-title":"Algorithms and Computation in Mathematics","volume":"5","author":"Jungnickel D.","year":"2005"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-6867-7_11"},{"key":"e_1_2_2_26_1","unstructured":"J. Leskovec. 2014. Stanford Network Analysis Package (SNAP). (2014). http:\/\/snap.stanford.edu\/index.html.  J. Leskovec. 2014. Stanford Network Analysis Package (SNAP). (2014). http:\/\/snap.stanford.edu\/index.html."},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"J.\n       \n      Maue\n     and \n      \n      \n      P.\n       \n      Sanders\n      \n  \n  . \n  2007\n  . Engineering algorithms for approximate weighted matching. In Proceedings of the 6th International Workshop on Experimental Algorithms (WEA\u201907) Lecture Notes in Computer Science Vol. \n  4525\n  . \n  Springer-Verlag 242--255.   J. Maue and P. Sanders. 2007. Engineering algorithms for approximate weighted matching. In Proceedings of the 6th International Workshop on Experimental Algorithms (WEA\u201907) Lecture Notes in Computer Science Vol. 4525. Springer-Verlag 242--255.","DOI":"10.1007\/978-3-540-72845-0_19"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741125"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS). 57","author":"Meyerhenke H."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2009.09.006"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_30"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the 18th European Symposium on Algorithms (ESA\u201910)","author":"Osipov V."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000814"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_32"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the 12th International Symposium on Experimental Algorithms. Springer, 164--175","author":"Sanders P."},{"key":"e_1_2_2_38_1","unstructured":"P. Sanders and C. Schulz. 2014. KaHIP\u2014Karlsruhe High Qualtity Partitioning Homepage. (2014). http:\/\/algo2.iti.kit.edu\/documents\/kahip\/index.html.  P. Sanders and C. Schulz. 2014. KaHIP\u2014Karlsruhe High Qualtity Partitioning Homepage. (2014). http:\/\/algo2.iti.kit.edu\/documents\/kahip\/index.html."},{"key":"e_1_2_2_39_1","unstructured":"C. Schulz. 2013. Hiqh Quality Graph Partititioning. Ph.D. dissertation. Karlsruhe Institute of Technology.  C. Schulz. 2013. Hiqh Quality Graph Partititioning. Ph.D. dissertation. Karlsruhe Institute of Technology."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOGO.0000042115.44455.f3"},{"key":"e_1_2_2_41_1","unstructured":"D. Spielman and N. Srivastava. 2008. Graph sparsification by effective resistances. CoRR abs\/0803.0929 (2008). http:\/\/arxiv.org\/abs\/0803.0929  D. Spielman and N. Srivastava. 2008. Graph sparsification by effective resistances. CoRR abs\/0803.0929 (2008). http:\/\/arxiv.org\/abs\/0803.0929"},{"key":"e_1_2_2_42_1","first-page":"146","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan R.","year":"1972","journal-title":"J. Comput."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03767-2_122"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2851496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2851496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:15Z","timestamp":1750221555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2851496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,29]]},"references-count":43,"alternative-id":["10.1145\/2851496"],"URL":"https:\/\/doi.org\/10.1145\/2851496","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,29]]}}}