Multilevel Algorithms for Acyclic Partitioning of Directed Acyclic Graphs

DOI10.1137/18M1176865zbMath1418.05108MaRDI QIDQ5230645

Bora Uçar, Kamer Kaya, M. Yusuf Özkaya, Julien Herrmann, Ümit V. Çatalyürek

Publication date: 28 August 2019

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

zbMATH Keywords

directed graphacyclic partitioningmultilevel partitioning

Mathematics Subject Classification ID

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

Uses Software

• METIS
• SparseMatrix
• ADMAT
• KaFFPa
• Scotch
• Chaco
• PaToH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch-and-bound algorithm for the acyclic partitioning problem
• Multilevel refinement for combinatorial optimisation problems
• Automatic Differentiation in MATLAB Using ADMAT with Applications
• On Characterizing the Data Access Complexity of Programs
• The university of Florida sparse matrix collection
• Engineering Multilevel Graph Partitioning Algorithms
• Fast (Structured) Newton Computations
• An Efficient Heuristic Procedure for Partitioning Graphs
• Graph Partitioning with Acyclicity Constraints
• Optimal Sequential Partitions of Graphs
• Benchmarking optimization software with performance profiles.

This page was built for publication: Multilevel Algorithms for Acyclic Partitioning of Directed Acyclic Graphs