Using domain decomposition to find graph bisectors

In this paper we introduce a three-step approach to find a vertex bisector of a graph. The first step finds a domain decomposition of the graph, consisting of a set of domains and a multisector. Each domain is a connected subgraph, and the multisector contains the remaining vertices that separate the domains from each other. The second step uses a block variant of the Kernighan-Lin scheme to find a bisector that is a subset of the multisector. The third step improves the bisector by bipartite graph matching. Experimental results show this domain decomposition method finds graph partitions that compare favorably with a state-of-the-art multilevel partitioning scheme in both quality and execution time.