Multilevel algorithms for acyclic partitioning of directed acyclic graphs. (English) Zbl 1418.05108


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
Full Text: DOI


[1] K. Agrawal, J. T. Fineman, J. Krage, C. E. Leiserson, and S. Toledo, Cache-conscious scheduling of streaming applications, in Proceedings of the Twenty-Fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA’12, 2012, pp. 236–245.
[2] T. N. Bui and C. Jones, A heuristic for reducing fill-in in sparse matrix factorization, in Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1993, pp. 445–452.
[3] Ü. V. Çatalyürek and C. Aykanat, PaToH: A Multilevel Hypergraph Partitioning Tool, Version \textup3.0, Department of Computer Engineering, Bilkent University, Ankara, Turkey, 1999; available online from http://cc.gatech.edu/ umit/software.html.
[4] T. F. Coleman and W. Xu, Parallelism in structured Newton computations, in Parallel Computing: Architectures, Algorithms and Applications, ParCo’07, Forschungszentrum Jülich and RWTH Aachen University, Jülich and Aachen, Germany, 2007, pp. 295–302.
[5] T. F. Coleman and W. Xu, Fast (structured) Newton computations, SIAM J. Sci. Comput., 31 (2008), pp. 1175–1191, https://doi.org/10.1137/070701005. · Zbl 1189.65098
[6] T. F. Coleman and W. Xu, Automatic Differentiation in MATLAB Using ADMAT with Applications, SIAM, Philadelphia, 2016, https://doi.org/10.1137/1.9781611974362. · Zbl 1364.65056
[7] J. Cong, Z. Li, and R. Bagrodia, Acyclic multi-way partitioning of Boolean networks, in Proceedings of the 31st ACM/IEEE Design Automation Conference, DAC’94, 1994, pp. 670–675.
[8] T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), 1. · Zbl 1365.65123
[9] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201–213. · Zbl 1049.90004
[10] V. Elango, F. Rastello, L.-N. Pouchet, J. Ramanujam, and P. Sadayappan, On characterizing the data access complexity of programs, in Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 567–580. · Zbl 1345.68101
[11] N. Fauzia, V. Elango, M. Ravishankar, J. Ramanujam, F. Rastello, A. Rountev, L.-N. Pouchet, and P. Sadayappan, Beyond reuse distance analysis: Dynamic analysis for characterization of data locality potential, ACM Trans. Archit. Code Optim., 10 (2013), 53.
[12] C. M. Fiduccia and R. M. Mattheyses, A linear-time heuristic for improving network partitions, in Proceedings of the 19th ACM/IEEE Design Automation Conference, DAC’82, 1982, pp. 175–181.
[13] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.
[14] B. Hendrickson and R. Leland, The Chaco User’s Guide, Version 1.0, Tech. Report SAND93–2339, Sandia National Laboratories, Albuquerque, NM, 1993.
[15] J. Herrmann, J. Kho, B. Uçar, K. Kaya, and Ü. V. Çatalyürek, Acyclic partitioning of large directed acyclic graphs, in Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID’17, 2017, pp. 371–380.
[16] G. Karypis and V. Kumar, MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0, Department of Computer Science and Engineering, Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998.
[17] B. W. Kernighan, Optimal sequential partitions of graphs, J. Assoc. Comput. Mach., 18 (1971), pp. 34–40.
[18] B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 49 (1970), pp. 291–307. · Zbl 0333.05001
[19] M. R. B. Kristensen, S. A. F. Lund, T. Blum, and J. Avery, Fusion of parallel array operations, in Proceedings of the 2016 ACM International Conference on Parallel Architectures and Compilation, 2016, pp. 71–85.
[20] M. R. B. Kristensen, S. A. F. Lund, T. Blum, K. Skovhede, and B. Vinter, Bohrium: A virtual machine approach to portable parallelism, in Proceedings of the IEEE International Parallel & Distributed Processing Symposium Workshops, IPDPSW’14, 2014, pp. 312–321.
[21] O. Moreira, M. Popp, and C. Schulz, Graph partitioning with acyclicity constraints, in 16th International Symposium on Experimental Algorithms, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Gernany, 2017. · Zbl 1433.68303
[22] O. Moreira, M. Popp, and C. Schulz, Evolutionary multi-level acyclic graph partitioning, in Proceedings of the ACM Genetic and Evolutionary Computation Conference, GECCO’18, 2018, pp. 332–339.
[23] J. Nossack and E. Pesch, A branch-and-bound algorithm for the acyclic partitioning problem, Comput. Oper. Res., 41 (2014), pp. 174–184. · Zbl 1348.90551
[24] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover, New York, 1998.
[25] F. Pellegrini, SCOTCH 5.1 User’s Guide, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Talence, France, 2008.
[26] L.-N. Pouchet, PolyBench/C: The Polyhedral Benchmark Suite, http://web.cse.ohio-state.edu/ pouchet/software/polybench/, 2012.
[27] P. Sanders and C. Schulz, Engineering multilevel graph partitioning algorithms, in Algorithms—ESA 2011, Springer, Berlin, Heidelberg, pp. 469–480. · Zbl 1346.05288
[28] C. Walshaw, Multilevel refinement for combinatorial optimisation problems, Ann. Oper. Res., 131 (2004), pp. 325–372. · Zbl 1067.90145
[29] E. S. H. Wong, E. F. Y. Young, and W. K. Mak, Clustering based acyclic multi-way partitioning, in Proceedings of the 13th ACM Great Lakes Symposium on VLSI, GLSVLSI ’03, 2003, pp. 203–206.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.