Relaxation-based coarsening and multiscale graph organization
Relaxation-based coarsening and multiscale graph organization
复制标题
DOI：
10.1137/100791142
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
D. Ron;Ilya Safro;A. Brandt
中科院分区：
文献类型：
--
作者：
D. Ron;Ilya Safro;A. Brandt
在本文中，我们推广和改进的多尺度组织的图，通过引入一个新的措施，量化的“接近度”之间的两个节点。测量的计算在图中的边的数量上是线性的，并且仅涉及少量的松弛扫描。然后计算类似的距离概念，并在每个较粗的级别使用。我们证明了使用这种措施在多尺度方法的几个重要的组合优化问题，并讨论了多尺度图组织。
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.