A graph partitioning algorithm by node separators

ABSTRACT

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.

REFERENCES

• 1: SERGE, C. Two theorems in graph theory. In Proceedings of the National Academy of Sciences 43, 1957, pp. 842-844.
• 2: SERGE, C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973.
• 3: Cox, P., BURCH, R., AND EPLER, B. Circuit partitioning for parallel processing. In Proceedings of the International Conference on Computer-Aided Design (Santa Clara, Calif., 1986), pp. 186-189.
• 4: DJIDJEV, H. N. On the problem of partitioning planar graphs. SIAM J. Algebraic Discrete Methods 3, (1982), 229-240.
• 5: I. S. Duff, On Algorithms for Obtaining a Maximum Transversal, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.315-330, Sept. 1981 [doi>10.1145/355958.355963]
• 6: Iain S. Duff , Torbjörn Wiberg, Remarks on implementation of O(n^1/2τ) assignment algorithms, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.267-287, Sept. 1988 [doi>10.1145/44128.44131]
• 7: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 8: Iain Duff , Roger Grimes , John Lewis , Bill Poole, Sparse matrix test problems, ACM SIGNUM Newsletter, v.17 n.2, p.22-22, June 1982 [doi>10.1145/1057588.1057590]
• 9: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 10: GEORGE, J.A. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10 {1973), 345-363.
• 11: GEORGE, J. A., AND LIU, J. W.H. An automatic nested dissection algorithm for irregular finite element problems. SIAM J. Numer. Anal. 15 (1978), 1053-1069.
• 12: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 13: A. George , W. H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review, v.31 n.1, p.1-19, Mar. 1989 [doi>10.1137/1031001]
• 14: John Russell Gilbert, Some nested dissection order is nearly optimal, Information Processing Letters, v.26 n.6, p.325-328, January 25, 1988 [doi>10.1016/0020-0190(88)90191-3]
• 15: J. R. Gilbert , R. E. Tarjan, The analysis of a nested dissection algorithm, Numerische Mathematik, v.50 n.4, p.377-404, FEB. 1987 [doi>10.1007/BF01396660]
• 16: John R. Gilbert , Earl Zmijewski, A Parallel Graph Partitioning Algorithm for a Message-Passing Multiprocessor, Cornell University, Ithaca, NY, 1987
• 17: HALL, P. On representatives of subsets. J. London Math. Society 10 (1935), 26-30.
• 18: HOPCROFT, J. E., AND KARP, R.M. An n**(~) algorithm for maximum matchings in bipartite graphs. SIAM Jr. Comput. 2 (1973), 225-231.
• 19: KERNIGHAN, B. W., AND LIN, S. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49 (1970), 291-307.
• 20: KIRKPATRmK, S., GELATT, C. D., JR., AND VECCm, M.P. Optimization by simulated annealing. Science 220 (1983), 671-680.
• 21: LEI'SERSON, C. Area-efficient graph layout (for VLSI). In Proceedings of the 21st Annual Symposium on the Foundations of Computer Science (1980), IEEE, New York, 1980, pp. 270-281.
• 22: Charles E. Leiserson , John G. Lewis, Orderings for Parallel Sparse Symmetric Factorization, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.27-31, December 01-04, 1987
• 23: LIPTON, R. J., AND TARJAN, R.E. A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979), 177-189.
• 24: LIPTON, R. J., AND TARJAN, R.E. Applications of a planar separator theorem. SIAM J. Comput. 9 (1980), 615-627.
• 25: Joseph W. H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.141-153, June 1985 [doi>10.1145/214392.214398]
• 26: Joseph W. Liu, A compact row storage scheme for Cholesky factors using elimination trees, ACM Transactions on Mathematical Software (TOMS), v.12 n.2, p.127-148, June 1986 [doi>10.1145/6497.6499]
• 27: LIU, J. W.H. The role of elimination trees in sparse factorization. Tech. Rep. CS-87-12, Dept. of Computer Science, York Univ., North York, Ontario, 1987. (To appear in SIAM J. Matrix Anal. Appl. )
• 28: Joseph W. H. Liu, Equivalent sparse matrix reordering by elimination tree rotations, SIAM Journal on Scientific and Statistical Computing, v.9 n.3, p.424-444, May 1988 [doi>10.1137/0909029]
• 29: LIU, J. W.H. On the minimum degree ordering with constraints. Tech. Rep. CS-88-02, Dept. of Computer Science, York Univ., North York, Ontario, May 1988.
• 30: L. Lovasz, Matching Theory (North-Holland mathematics studies), Elsevier Science Ltd, 1986
• 31: Doug W. Moore, A Round-Robin Parallel Partitioning Algorithm, Cornell University, Ithaca, NY, 1988
• 32: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 33: ROSE, D.J. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In Graph Theory and Computing, R. Read, Ed. Academic Press, Orlando, Fla., 1972, pp. 183-217.
• 34: Robert Schreiber, A New Implementation of Sparse Gaussian Elimination, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.256-276, Sept. 1982 [doi>10.1145/356004.356006]
• 35: Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
• 36: YANNAKAKIS, M. Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2 (1981), 77-79.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Algorithms