Title :
Two-way graph partitioning by principal components
Author :
Rao, Vasant B. ; Arun, K.S.
Author_Institution :
Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA
Abstract :
The problem of partitioning the vertex set of an edge-weighted undirected graph into two parts of specified sizes so that the sum of the weights on edges joining vertices in different parts is minimum is addressed. This problem is NP-hard, and has several important applications in VLSI layout. An approach based on principal components analysis is proposed to develop several heuristics for the above two-way graph-partitioning problem. These heuristics generate partitions directly from a couple of eigenvectors of a certain matrix derived from the connection matrix of a graph. Lower bounds on the cost of an optimal partition are derived. Some experimental results and a comparison of the computation time of the heuristics are shown
Keywords :
VLSI; circuit layout; computational complexity; graph theory; network topology; NP-hard problem; VLSI layout; computation time; edge-weighted undirected graph; eigenvectors; heuristics; principal components; principal components analysis; two-way graph-partitioning; Cost function; Iterative algorithms; Matrix decomposition; Partitioning algorithms; Principal component analysis; Simulated annealing; Stochastic processes; Symmetric matrices; Very large scale integration; Wafer scale integration;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112611
