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

Applications of Dulmage-Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement

Cleve Ashcraft and Joseph W.H. Liu

Technical Report CS-96-05

York University

August 16, 1996


In this paper, we consider the use of the Dulmage-Mendelsohn decomposition and network flow on bipartite graphs in improving a graph bisection partition. Given a graph partition [S,B,W] with a vertex separator S and two disconnected components B and W, different strategies are considered based on the Dulmage-Mendelsohn decomposition in reducing the separator size |S| and/or the imbalance between B and W. For the case when the vertices are weighted, we relate this with the network flow problem. Experimental results are provided to demonstrate that these techniques can be used in improving good graph bisection partitions from existing partitioning schemes.

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.