Advertisement
Published in:
2010 | OriginalPaper | Chapter
Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization
Author : Henning Meyerhenke
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we study the prevalent problem of graph partitioning by analyzing the diffusion-based partitioning heuristic
Bubble
-FOS/C, a key component of the practically successful partitioner
DibaP
[14]. Our analysis reveals that
Bubble
-FOS/C, which yields well-shaped partitions in experiments, computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). It therefore provides the first substantial theoretical insights (beyond intuition) why
Bubble
-FOS/C (and therefore indirectly
DibaP
) yields good experimental results. Moreover, we show that in bisections computed by
Bubble
-FOS/C, at least one of the two parts is connected. Using arguments based on random walk techniques, we prove that in vertex-transitive graphs actually both parts must be connected components each. All these results may help to eventually bridge the gap between practical and theoretical graph partitioning.