{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,17]],"date-time":"2026-10-17T17:21:37Z","timestamp":1792257697857,"version":"4.4.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We investigate the problem of partitioning the vertices of a directed acyclic graph into a given number of parts. The objective function is to minimize the number or the total weight of the edges having end points in different parts, which is also known as the edge cut. The standard load balancing constraint of having an equitable partition of the vertices among the parts should be met. Furthermore, the partition is required to be acyclic; i.e., the interpart edges between the vertices from different parts should preserve an acyclic dependency structure among the parts. In this work, we adopt the multilevel approach with coarsening, initial partitioning, and refinement phases for acyclic partitioning of directed acyclic graphs. We focus on two-way partitioning (sometimes called bisection), as this scheme can be used in a recursive way for multiway partitioning. To ensure the acyclicity of the partition at all times, we propose novel and efficient coarsening and refinement heuristics. The quality of the computed acyclic partitions is assessed by computing the edge cut. We also propose effective ways to use the standard undirected graph partitioning methods in our multilevel scheme. We perform a large set of experiments on a dataset consisting of (i) graphs coming from an application and (ii) some others corresponding to matrices from a public collection. We report significant improvements compared to the current state of the art.<\/jats:p>","DOI":"10.1137\/18m1176865","type":"journal-article","created":{"date-parts":[[2019,7,3]],"date-time":"2019-07-03T12:34:00Z","timestamp":1562157240000},"page":"A2117-A2145","source":"Crossref","is-referenced-by-count":46,"title":["Multilevel Algorithms for Acyclic Partitioning of Directed Acyclic Graphs"],"prefix":"10.1137","volume":"41","author":[{"given":"Julien","family":"Herrmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. Yusuf","family":"\u00d6zkaya","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bora","family":"U\u00e7ar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kamer","family":"Kaya","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00dcmit V.","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,7,3]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312049"},{"key":"atypb2","first-page":"445","volume-title":"Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, SIAM","author":"Bui T. N.","year":"1993"},{"key":"atypb3","volume-title":"Version \\textup3.0, Department of Computer Engineering","author":"\u00c7ataly\u00fcrek \u00dc. V.","year":"1999"},{"key":"atypb4","first-page":"295","volume-title":"Parallel Computing: Architectures, Algorithms and Applications, ParCo'07","author":"Coleman T. F.","year":"2007"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/070701005"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974362"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/196244.196609"},{"key":"atypb8","first-page":"1","volume":"38","author":"Davis T. A.","year":"2011","journal-title":"ACM Trans. Math. Software"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"atypb10","first-page":"567","volume-title":"Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"Elango V."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/2541228.2555309"},{"key":"atypb12","first-page":"175","volume-title":"Proceedings of the 19th ACM\/IEEE Design Automation Conference, DAC'82","author":"Fiduccia C. M.","year":"1982"},{"key":"atypb13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland,\n                      The Chaco User's Guide, Version 1.0\n                      , Tech. Report SAND93-2339, Sandia National Laboratories, Albuquerque, NM, 1993.","DOI":"10.2172\/10106339"},{"key":"atypb15","first-page":"371","volume-title":"Proceedings of the 17th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID'17","author":"Herrmann J.","year":"2017"},{"key":"atypb16","volume-title":"Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0, Department of Computer Science and Engineering","author":"Karypis G.","year":"1998"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321627"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/2967938.2967945"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2014.44"},{"key":"atypb21","volume-title":"16th International Symposium on Experimental Algorithms, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik","author":"Moreira O.","year":"2017"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/3205455.3205464"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2013.08.013"},{"key":"atypb24","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1998"},{"key":"atypb25","volume-title":"Laboratoire Bordelais de Recherche en Informatique (LaBRI)","author":"Pellegrini F.","year":"2008"},{"key":"atypb26","unstructured":"L.N. Pouchet,\n                      PolyBench\/C: The Polyhedral Benchmark Suite\n                      ,http:\/\/web.cse.ohio-state.edu\/~pouchet\/software\/polybench\/, 2012."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_40"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1023\/B:ANOR.0000039525.80601.15"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/764808.764860"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1176865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:17:11Z","timestamp":1787325431000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1176865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1176865"],"URL":"https:\/\/doi.org\/10.1137\/18m1176865","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}