Relaxation-Based Coarsening and Multiscale Graph Organization
Authors:
- Dorit RonDRDorit Ron
- Ilya SafroISIlya Safro
- Achi BrandtABAchi Brandt
- 1 January 2011
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in Multiscale Modeling & Simulation
- Vol. 9 (1) , 407-423
Abstract
In this paper we generalize and improve the multiscale organization of graphs by introducing a new measure that quantifies the “closeness” between two nodes. The calculation of the measure is linear in the number of edges in the graph and involves just a small number of relaxation sweeps. A similar notion of distance is then calculated and used at each coarser level. We demonstrate the use of this measure in multiscale methods for several important combinatorial optimization problems and discuss the multiscale graph organization.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Diffusion mapsApplied and Computational Harmonic Analysis, 2006
- A Multilevel Algorithm for Wavefront ReductionSIAM Journal on Scientific Computing, 2001
- Renormalization Multigrid (RMG): Statistically Optimal Renormalization Group Flow and Coarse-to-Fine Monte Carlo AccelerationJournal of Statistical Physics, 2001
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- An Analysis of Spectral Envelope Reduction via Quadratic Assignment ProblemsSIAM Journal on Matrix Analysis and Applications, 1997
- Genetic algorithm and graph partitioningIEEE Transactions on Computers, 1996
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- Algebraic multigrid theory: The symmetric caseApplied Mathematics and Computation, 1986
- Multi-level adaptive solutions to boundary-value problemsMathematics of Computation, 1977
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970