Multi-level direct \(K\)-way hypergraph partitioning with multiple constraints and fixed vertices

DOI10.1016/j.jpdc.2007.09.006zbMath1243.68222OpenAlexW4300646857MaRDI QIDQ436766

B. Barla Cambazoglu, Cevdet Aykanat, Bora Uçar

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.09.006

zbMATH Keywords

direct \(K\)-way refinementfixed verticeshypergraph partitioningmulti-constraintmulti-level paradigmrecursive bisection

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

A reductive approach to hypergraph clustering: an application to image segmentation, Improving Unstructured Mesh Partitions for Multiple Criteria Using Mesh Adjacencies, An exact approach for the multi-constraint graph partitioning problem, A survey of direct methods for sparse linear systems, A Matrix Partitioning Interface to PaToH in MATLAB, Least Squares Estimators of Peptide Species Concentrations Based on Gaussian Mixture Decompositions of Protein Mass Spectra, Communication Avoiding ILU0 Preconditioner, Network Flow-Based Refinement for Multilevel Hypergraph Partitioning

Uses Software

• METIS
• SparseMatrix
• Zoltan
• Chaco
• PaToH
• hMETIS

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel image restoration using surrogate constraint methods
• Adaptive decomposition and remapping algorithms for object-space-parallel direct volume rendering of unstructured grids
• Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories
• Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models
• Recent directions in netlist partitioning: a survey
• Partitioning Sparse Matrices for Parallel Preconditioned Iterative Methods
• An Efficient Heuristic Procedure for Partitioning Graphs
• Improving the Run Time and Quality of Nested Dissection Ordering
• How Good is Recursive Bisection?
• Encapsulating Multiple Communication-Cost Metrics in Partitioning Sparse Rectangular Matrices for Parallel Matrix-Vector Multiplies
• Permuting Sparse Rectangular Matrices into Block-Diagonal Form
• Compressed Graphs and the Minimum Degree Algorithm
• A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
• Revisiting Hypergraph Models for Sparse Matrix Partitioning
• Multiphase mesh partitioning