A heuristic graph partitioning scheme is presented to determine effective node separators for undirected graphs. An initial separator is first obtained from the minimum degree ordering, an algorithm designed originally to produce fill-reducing orderings for sparse matrices. The separator is then improved by an iterative strategy based on some known results from bipartite graph matching. This gives an overall practical scheme in partitioning graphs. Experimental results are provided to demonstrate the effectiveness of this heuristic algorithm on graphs arising from sparse matrix applications.
No takes yet. Share an insight, caveat, or question.
Joseph W. H. Liu (1989) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: