Using Domain Decomposition to find Graph Bisectors
Cleve Ashcraft and Joseph W.H. Liu
Technical Report CS-95-08
York University
November 11, 1995
Abstract
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, a set of connected subgraphs, the domains, and a multisector, 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 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.
Download paper in PDF format.
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.