Spectral K-way ratio-cut partitioning and clustering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spectral K-way ratio-cut partitioning and clustering

Full text

Pdf (695 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 30th international Design Automation Conference table of contents

Dallas, Texas, United States

Pages: 749 - 754

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

Pak K. Chan
Martine D. F. Schlag
Jason Y. Zien

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 29, Downloads (12 Months): 108, Citation Count: 26

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/157485.165117 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. R. Barnes. An algorithm for partitioning the nodes of a graph. SIAM J. on Algorithm and Discrete Method, 3(4):541-550, Dec. 1982.
	2	R. Boppana. Eigenvalues and graph bisection: An average-case analysis. FOCS, pg. 280-285, 1987.
	3	Pak K. Chan , Martine Schlag , Jason Y. Zien, Spectral k-way ratio-cut partitioning and clustering, Proceeding of the 1993 symposium on Research on integrated systems, p.123-142, February 1993, Seattle, Washington, United States
	4	C.K. Cheng and T. C. Hu. The optimal partitioning of networks. Tech Report CS89-146, UC San Diego, March 1989.
	5	C.-K. Cheng and Y.-C. A. Wei. An improved twoway partitioning algorithm with stable performance. IEEE Trans. on CAD, 10(12):1502-1511, Dec. 1991.
	6	D. M. Cvetkovic, M. Doob, and H. Sachs. Spectra of Graphs: Theory and Application. Academic Press, Inc., New York, New York, 1979.
	7	W. Donath and A. Hoffman. Lower bounds for the partitioning of graphs. IBM J. ReiD, pg. 420-425, 1973.
	8	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
	9	M. Fiedler. Special matrices and their applications in numerical mathematics. Martinus Nijhoff Pubfishers, 1986.
	10	Jonathan A. Frantde. Circuit placement methods using multiple eigenvectors and linear probe techniques. Tech Report UCB/ERL M87/32, May 1987.
	11	S. W. Hadley, B. L. Mark, and A. Vanelli. An Efficient Eigenvector Approach for Finding Netlist Partitions. IEEE Trans. on CAD, CAD-11(7):885- 892, July 1992.
	12	L. Hagen and A. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Trans. on CAD, CAD-11(9):1074-1085, Sept. 1992.
	13	K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17(3):219-229, Nov. 1970.
	14	B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. The BSTJ, pg. 291-307, Feb 1970.
	15	B. Krishnamurthy. An Improved Min-Cut Algorithm For Partitioning VLSI Networks. IEEE Trans. on Comp., C-33(5):438-446, May 1984.
	16	T. Leighton and S. Rao. An approximate maxflow min-cut theorem for uniform multicommodity flow problems with applications to approximate algorithms. FOCS 29, 1988.
	17	Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
	18	Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
	19	L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
	20	Ching-Wei Yeh , Chung-Kuan Cheng , Ting-Ting Y. Lin, A probabilistic multicommodity-flow solution to circuit clustering problems, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.428-431, November 1992, Santa Clara, California, United States
	21	J. Y. Zien. Spectral k-way ratio cut partitioning. Master's thesis, UC Santa Cruz, Mar. 1993.

CITED BY 26

	Roman Kužnar , Franc Brglez , Baldomir Zajc, Multi-way netlist partitioning into heterogeneous FPGAs and minimization of total device cost and interconnect, Proceedings of the 31st annual conference on Design automation, p.238-243, June 06-10, 1994, San Diego, California, United States
	Bernhard M. Riess , Konrad Doll , Frank M. Johannes, Partitioning very large circuits using analytical placement techniques, Proceedings of the 31st annual conference on Design automation, p.646-651, June 06-10, 1994, San Diego, California, United States
	J. Song , Z. Shen , W. Zhuang, An effective general connectivity concept for clustering, Proceedings of the conference on Design, automation and test in Europe, p.398-405, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Roman Kužnar , Franc Brglez, PROP: a recursive paradigm for area-efficient and performance oriented partitioning of large FPGA netlists, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.644-649, November 05-09, 1995, San Jose, California, United States
	Jason Cong , Sung Kyu Lim, Multiway partitioning with pairwise movement, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.512-516, November 08-12, 1998, San Jose, California, United States
	Roman Kužnar , Baldomir Zajc , Franc Brglez, A unified cost model for min-cut partitioning with replication applied to optimization of large heterogeneous FPGA partitions, Proceedings of the conference on European design automation, p.271-276, September 19-23, 1994, Grenoble, France
	Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States
	Sverre Wichlund, On multilevel circuit partitioning, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.505-511, November 08-12, 1998, San Jose, California, United States
	George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States
	Nan-Chi Chou , Lung-Tien Liu , Chung-Kuan Cheng , Wei-Jin Dai , Rodney Lindelof, Circuit partitioning for huge logic emulation systems, Proceedings of the 31st annual conference on Design automation, p.244-249, June 06-10, 1994, San Diego, California, United States
	Jason Cong , Wilburt Labio , Narayanan Shivakumar, Multi-way VLSI circuit partitioning based on dual net representation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.56-62, November 06-10, 1994, San Jose, California, United States
	Eric S. H. Wong , Evangeline F. Y. Young , W. K. Mak, Clustering based acyclic multi-way partitioning, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA
	Thang Nguyen Bui , Byung Ro Moon, A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs, Proceedings of the 31st annual conference on Design automation, p.664-669, June 06-10, 1994, San Diego, California, United States
	Bo Long , Zhongfei (Mark) Zhang , Philip S. Yu, Co-clustering by block value decomposition, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Bo Long , Zhongfei (Mark) Zhang , Xiaoyun Wú , Philip S. Yu, Spectral clustering for multi-type relational data, Proceedings of the 23rd international conference on Machine learning, p.585-592, June 25-29, 2006, Pittsburgh, Pennsylvania
	Bo Long , Xiaoyun Wu , Zhongfei (Mark) Zhang , Philip S. Yu, Unsupervised learning on k-partite graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Bo Long , Zhongfei (Mark) Zhang , Xiaoyun Wu , Philip S. Yu, Relational clustering by symmetric convex coding, Proceedings of the 24th international conference on Machine learning, p.569-576, June 20-24, 2007, Corvalis, Oregon
	B. M. Riess , A. A. Schoene, Architecture driven k-way partitioning for multichip modules, Proceedings of the 1995 European conference on Design and Test, p.71, March 06-09, 1995
	Melanie Elm , Hans-Joachim Wunderlich , Michael E. Imhof , Christian G. Zoellin , Jens Leenstra , Nicolas Maeding, Scan chain clustering for test power reduction, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Miklos Kurucz , Andras Benczur , Karoly Csalogany , Laszlo Lukacs, Spectral clustering in telephone call graphs, Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, p.82-91, August 12-12, 2007, San Jose, California
	Qiaozhu Mei , Deng Cai , Duo Zhang , ChengXiang Zhai, Topic modeling with network regularization, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Bo Long , Zhongfei Mark Zhang , Philip S. Yu, A probabilistic framework for relational clustering, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Melanie Elm , Hans-Joachim Wunderlich, Scan chain organization for embedded diagnosis, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
	Bo Long , Mark Zhang , Philip S. Yu, Graph partitioning based on link distributions, Proceedings of the 22nd national conference on Artificial intelligence, p.578-583, July 22-26, 2007, Vancouver, British Columbia, Canada
	Jianhua Ruan , Weixiong Zhang, Identification and evaluation of weak community structures in networks, Proceedings of the 21st national conference on Artificial intelligence, p.470-475, July 16-20, 2006, Boston, Massachusetts
	Bo Long , Mark Zhang , Philip S. Yu , Tianbing Xu, Clustering on complex graphs, Proceedings of the 23rd national conference on Artificial intelligence, p.659-664, July 13-17, 2008, Chicago, Illinois