Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
1995 Technical Reports

Using Domain Decomposition to find Graph Bisectors

Cleve Ashcraft and Joseph W.H. Liu

Technical Report CS-95-08

York University

November 11, 1995


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.