Title :
A ratio-cut partitioning algorithm using node contraction
Author_Institution :
Dept. of Comput. Eng. & Comput. Sci., Missouri Univ., Columbia, MO, USA
Abstract :
This paper describes a new simple ratio-cut partitioning algorithm using node contraction. This new algorithm combines iterative improvement with progressive cluster formation. Under suitably mild assumptions, the new algorithm runs in linear time. It is also shown that the new algorithm compares favorably with previous approaches
Keywords :
circuit analysis computing; graph theory; iterative methods; network topology; iterative improvement; linear time algorithm; node contraction; progressive cluster formation; ratio-cut partitioning algorithm; Circuits; Clustering algorithms; Computer science; Costs; Cyclic redundancy check; Iterative algorithms; Iterative methods; Partitioning algorithms;
Conference_Titel :
Circuits and Systems, 1999. 42nd Midwest Symposium on
Conference_Location :
Las Cruces, NM
Print_ISBN :
0-7803-5491-5
DOI :
10.1109/MWSCAS.1999.867245
