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 8 articles )
Showing results 1 to 8 of 8.
- Fu, Lin; Litvinov, Sergej; Hu, Xiangyu Y.; Adams, Nikolaus A.: A novel partitioning method for block-structured adaptive meshes (2017)
- Schornbaum, Florian; Rüde, Ulrich: Massively parallel algorithms for the lattice Boltzmann method on nonuniform grids (2016)
- Safro, Ilya; Sanders, Peter; Schulz, Christian: Advanced coarsening schemes for graph partitioning (2014)
- Liu, Peng; Wang, Chao-Fu: A bubble-inspired algorithm for finite element mesh partitioning (2013)
- 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)