Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning

DOI10.1137/17M1152735zbMath1419.05160arXiv1710.06552OpenAlexW3101642221MaRDI QIDQ5197618

Ruslan Shaydulin, Ilya Safro, Jie Chen

Publication date: 19 September 2019

Published in: Multiscale Modeling & Simulation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.06552

zbMATH Keywords

matchingcoarseningmultilevel algorithmshypergraph partitioningcombinatorial scientific computingvertex similarity measure

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Large-scale problems in mathematical programming (90C06) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs (65M55)

Related Items

Leveraging special-purpose hardware for local search heuristics, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm

Uses Software

• Trilinos
• SNAP
• SparseMatrix
• KaFFPa
• Zoltan
• PaToH
• KaHyPar
• NetworKit
• Graclus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel multilevel algorithms for hypergraph partitioning
• Multiscale approach for the network compression-friendly ordering
• A multilevel bilinear programming algorithm for the vertex separator problem
• Spectra, Euclidean representations and clusterings of hypergraphs
• Modeling hypergraphs by graphs with the same mincut properties
• A multi-level hypergraph partitioning algorithm using rough set clustering
• Algebraic connectivity of an even uniform hypergraph
• A Multilevel Algorithm for Wavefront Reduction
• Advanced Coarsening Schemes for Graph Partitioning
• The university of Florida sparse matrix collection
• Relaxation-Based Coarsening and Multiscale Graph Organization
• Engineering Multilevel Graph Partitioning Algorithms
• Algebraic Distance on Graphs
• Recent directions in netlist partitioning: a survey
• An overview of the Trilinos project
• An Efficient Heuristic Procedure for Partitioning Graphs
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A Multigrid Tutorial, Second Edition
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• 10.1162/153244303321897735
• k-way Hypergraph Partitioning via n-Level Recursive Bisection
• Engineering a direct k-way Hypergraph Partitioning Algorithm
• A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
• Graph minimum linear arrangement by multilevel weighted edge contractions
• Graclus