Multilevel algorithms for acyclic partitioning of directed acyclic graphs

DOI10.1137/18M1176865MaRDI QIDQ5230645zbMATH OpenFDO

Authors Julien Herrmann, M. Yusuf Özkaya, Bora Uçar, Kamer Kaya, Ü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

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

Recommendations

• scientific article; zbMATH DE number 2084263
• Graph partitioning with acyclicity constraints
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A partitioning requiring rapidity and quality: the multilevel method and partitions refinement algorithms
• \(n\)-level graph partitioning

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• A branch-and-bound algorithm for the acyclic partitioning problem
• An Efficient Heuristic Procedure for Partitioning Graphs
• Automatic differentiation in MATLAB using ADMAT with applications
• Benchmarking optimization software with performance profiles.
• Engineering multilevel graph partitioning algorithms
• Fast (structured) Newton computations
• Graph partitioning with acyclicity constraints
• Multilevel refinement for combinatorial optimisation problems
• On characterizing the data access complexity of programs
• Optimal Sequential Partitions of Graphs
• Parallelism in structured Newton computations
• The University of Florida sparse matrix collection

Cited in

(3)

• Multi-level direct \(K\)-way hypergraph partitioning with multiple constraints and fixed vertices
• Graph partitioning with acyclicity constraints
• A modified DIRECT algorithm with bilevel partition

Describes a project that uses

Uses Software

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

This page was built for publication: Multilevel algorithms for acyclic partitioning of directed acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230645)