How Good is Recursive Bisection?

DOI10.1137/S1064827593255135zbMath0886.68104OpenAlexW1971758446MaRDI QIDQ4376226

Horst D. Simon, Shang-Hua Teng

Publication date: 10 February 1998

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

Full work available at URL: https://doi.org/10.1137/s1064827593255135

zbMATH Keywords

parallel processingload balancingmesh partitioningrecursive bisectioncommunication costscalable parallel algorithmsdata and computation mapping on parallel machineswell-shaped finite-element and finite-difference meshes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (25)

Multiway \(p\)-spectral graph cuts on Grassmann manifolds ⋮ On minimum bisection and related partition problems in graphs with bounded tree width ⋮ Approximating minimum \(k\)-section in trees with linear diameter ⋮ COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗ ⋮ Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Quasi-Monte Carlo Methods for Binary Event Models with Complex Family Data ⋮ Corner cuts are close to optimal: from solid grids to polygons and back ⋮ Multi-level direct \(K\)-way hypergraph partitioning with multiple constraints and fixed vertices ⋮ Dynamic Balanced Graph Partitioning ⋮ Load-Balancing for Parallel Delaunay Triangulations ⋮ An efficient approach for large scale graph partitioning ⋮ Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation ⋮ Combinatorial optimization of the discretized multiphase Mumford-Shah functional ⋮ A graph partitioning strategy for solving large-scale crew scheduling problems ⋮ Min-max-boundary domain decomposition ⋮ Spectral clustering with physical intuition on spring-mass dynamics ⋮ Deterministic Parallel Hypergraph Partitioning ⋮ \(K\)-means clustering for optimal partitioning and dynamic load balancing of parallel hierarchical \(N\)-body simulations ⋮ Edge integrity of nearest neighbor graphs and separator theorems ⋮ Node adaptive domain decomposition method by radial basis functions ⋮ Optimal block-tridiagonalization of matrices for coherent charge transport ⋮ A GRAPH BASED DAVIDSON ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM ⋮ Balanced partitions of trees and applications ⋮ On the bandwidth of the Kneser graph

This page was built for publication: How Good is Recursive Bisection?