Parallel multilevel algorithms for hypergraph partitioning

DOI10.1016/j.jpdc.2007.11.002zbMath1243.68318OpenAlexW2042088790WikidataQ29394539 ScholiaQ29394539MaRDI QIDQ436760

Aleksandar Trifunović, William J. Knottenbelt

Publication date: 26 July 2012

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jpdc.2007.11.002

zbMATH Keywords

load balancingdata partitioningparallel graph partitioningparallel hypergraph partitioningparallel sparse matrixsparse matrix decompositionvector multiplicationVLSI circuit design

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm, A discrete dynamic convexized method for VLSI circuit partitioning, Network Flow-Based Refinement for Multilevel Hypergraph Partitioning

Uses Software

• SparseMatrix
• ParMETIS
• MPI
• Zoltan
• PaToH
• hMETIS
• Parkway

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• DNA electrophoresis studied with the cage model
• Finding good approximate vertex and edge partitions is NP-hard
• Hypergraph-based parallel computation of passage time densities in large semi-Markov models
• Graph partitioning models for parallel computing
• New challenges in dynamic load balancing
• Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models
• Recent directions in netlist partitioning: a survey
• An Improved Min-Cut Algonthm for Partitioning VLSI Networks
• An Efficient Heuristic Procedure for Partitioning Graphs
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• Parallel static and dynamic multi‐constraint graph partitioning
• Encapsulating Multiple Communication-Cost Metrics in Partitioning Sparse Rectangular Matrices for Parallel Matrix-Vector Multiplies
• Permuting Sparse Rectangular Matrices into Block-Diagonal Form
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication