Spectral K-way Ratio-cut Partitioning: Preliminary results, Part 1

Front Cover
University of California, Santa Cruz, Computer Research Laboratory, 1992 - Computer-aided design - 12 pages
Abstract: "Recent research on partitioning has focussed on the ratio-cut cost metric which maintains a balance between the sizes of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two- way ratio-cut partitioning have yielded higher quality partitioning results. In this paper we develop a spectral approach to multi-way ratio- cut partitioning which provides a generalization of the ratio-cut cost metric to k-way partitioning and a lower bound on this cost metric. Our approach uses Lanczos algorithm to find the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors are used to construct an orthogonal projection to map a vertex (of the graph) in an n-dimensional space into a k-dimensional subspace. We exploit the (near) orthogonality of the projected points to effect high quality clustering of points in a k-dimensional subspace. An efficient algorithm is presented for coercing the points in the k-dimensional subspace into k-partitions. Advancement over the current work is evidenced by the results of experiments on the standard MCNC benchmarks."

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Common terms and phrases

Bibliographic information