Beyond good partition shapes: an analysis of diffusive graph partitioning. ... We then regard Bubble-FOS/C, which has been shown in previous experiments to produce solutions with good partition shapes and other favorable properties. In this paper we prove that it computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). This result provides the first substantial theoretical insight why Bubble-FOS/C yields good experimental results in terms of graph partitioning metrics. Moreover, we show that in bisections computed by Bubble-FOS/C, at least one of the two parts is connected. Using the aforementioned relation between FOS/C and random walks, we prove that in vertex-transitive graphs both parts must be connected components.
Keywords for this software
References in zbMATH (referenced in 5 articles )
Showing results 1 to 5 of 5.
- Schornbaum, Florian; Rüde, Ulrich: Massively parallel algorithms for the lattice Boltzmann method on nonuniform grids (2016)
- Meyerhenke, Henning; Sauerwald, Thomas: Beyond good partition shapes: an analysis of diffusive graph partitioning (2012)
- Benlic, Una; Hao, Jin-Kao: An effective multilevel tabu search approach for balanced graph partitioning (2011)
- Galinier, Philippe; Boujbel, Zied; Coutinho Fernandes, Michael: An efficient memetic algorithm for the graph partitioning problem (2011)
- Ron, Dorit; Safro, Ilya; Brandt, Achi: Relaxation-based coarsening and multiscale graph organization (2011)