IEEE Transactions on Computers · 1989 · 386 citations · 10 references
ComputingComputer ScienceAlgorithmsData StructuresOptimizationData PartitioningNetwork TopologyComplexity AnalysisData Partitioning StrategiesGainIterative ImprovementLevelsNetwork PartitioningPartitioning AlgorithmsPartitioning Strategies
A multiple-block network partitioning algorithm adapted from a two-block iterative improvement partitioning algorithm is presented. This adaptation of the algorithm and of the level gain concept to multiple blocks seeks to improve the partition uniformly with respect to all blocks as oppose to making repeated uses of two-way partitioning. Appropriate data structures and a complexity analysis are presented, as well as experimental results. The experiments indicate that the optimal number of levels to use depends on the number of blocks and the net size and degree distributions of the network, but it varies little with the size of the network. In particular, higher levels are increasingly useful as the number of blocks in the partition increases. Theoretical results agree with the experimental results and form the basis for a predictor which, given a network and the desired number of blocks, approximates the optimal number of levels.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
10
Multiple-way network partitioning
Laura A. Sanchis · IEEE Transactions on Computers · 1989 · 386 citations
Graph bisection algorithms with good average case behavior
Thanh‐Tung Bui, S.K. Chaudhuri, F. T. Leighton et al. · COMBINATORICA · 1987 · 327 citations