Spectral partitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spectral partitioning: the more eigenvectors, the better

Full text

Pdf (708 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 32nd annual ACM/IEEE Design Automation Conference table of contents

San Francisco, California, United States

Pages: 195 - 200

Year of Publication: 1995

ISBN:0-89791-725-1

Authors

Charles J. Alpert	UCLA Computer Science Department, Los Angeles, CA
So-Zen Yao	Cadence Design Systems, San Jose, CA

Sponsors

EDAC : Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 53, Citation Count: 25

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/217474.217529 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	C. J. Alpert , A. B. Kahng, Geometric embeddings for faster and better multi-way netlist partitioning, Proceedings of the 30th international conference on Design automation, p.743-748, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165115]
	2	C. J. Alpert , A. B. Kahng, Multi-way partitioning via spacefilling curves and dynamic programming, Proceedings of the 31st annual conference on Design automation, p.652-657, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196603]
	3	C. J. Alpert , A. B. Kahng, A general framework for vertex orderings, with applications to netlist clustering, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.63-67, November 06-10, 1994, San Jose, California, United States
	4	Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
	5	C. J. Alpert and S.-Z. Yao, "Spectral Partitioning: The More Eigenvectors, the Better," UCLA CS Dept. Technical Report, #940036, October 1994.
	6	E. R. Barnes, "An Algorithm for Partitioning the Nodes of a Graph," Siam J. Algorithms and Discrete Methods (3)4, 1992, pp. 541-549.
	7	P.K. Chan, M. D. F. Schlag and J. Zien, "Spectral K-Way Ratio Cut Partitioning and Clustering", IEEE Trans. on CAD 13(9), 1994, pp. 1088-1096.
	8	J. Frankle and R. M. Karp, "Circuit Placements and Cost Bounds by Eigenvector Decomposition," IEEE Conf. Computer Aided Design, 1986, pp. 414-417
	9	J. Garbers, H. J. Promel and A. Steger, "Finding Clusters in VLSI Circuits" Proc. IEEE Intl. Conf. on Computer-Aided Design, 1990, pp. 520-523.
	10	L. Hagen and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering", Proc. IEEE Intl. Conf. Computer-Aided Design, 1991, pp. 10-13.
	11	Lars Hagen , Andrew B. Kahng, A new approach to effective circuit clustering, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.422-427, November 1992, Santa Clara, California, United States
	12	K. M. Hall, "An r-dimensional Quadratic Placement Algorithm", Manag. Sci., 17(1970), pp. 219-229.
	13	B. Mohar, "The Laplacian Spectrum of Graphs", Proc. 6th Quadrennial Intl. Conf. on Theory and Applications of Graphs, 1988, pp. 871-898.
	14	F. Rendl and H. Wolkowicz, "A Projection Technique for Partitioning the Nodes of a Graph", Univ. Waterloo Technical Report, May 1994.
	15	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 [doi>10.1145/196244.196602]

CITED BY 25

	John M. Emmert , Sandeep Lodha , Dinesh K. Bhatia, On Using Tabu Search for Design Automation of VLSI Systems, Journal of Heuristics, v.9 n.1, p.75-90, January 2003
	Morgan Enos , Scott Hauck , Majid Sarrafzadeh, Replication for logic bipartitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.342-349, November 09-13, 1997, San Jose, California, United States
	Huiqun Liu , Kai Zhu , D. F. Wong, Circuit partitioning with complex resource constraints in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.77-84, February 22-25, 1998, Monterey, California, United States
	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
	Lung-Tien Liu , Ming-Ter Kuo , Shih-Chen Huang , Chung-Kuan Cheng, A gradient method on the initial partition of Fiduccia-Mattheyses algorithm, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.229-234, November 05-09, 1995, San Jose, 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
	Shantanu Dutt , Wenyong Deng, Cluster-aware iterative improvement techniques for partitioning large VLSI circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.91-121, January 2002
	Jason Y. Zien , Pak K. Chan , Martine Schlag, Hybrid spectral/iterative partitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.436-440, November 09-13, 1997, San Jose, California, United States
	Vi Chi Chan , David Lewis, Hierarchical partitioning for field-programmable systems, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.428-435, November 09-13, 1997, San Jose, California, United States
	Jason Cong , Honching Peter Li , Sung Kyu Lim , Toshiyuki Shibuya , Dongmin Xu, Large scale circuit partitioning with loose/stable net removal and signal flow based clustering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.441-446, November 09-13, 1997, San Jose, California, United States
	Shantanu Dutt , Wenyong Deng, A probability-based approach to VLSI circuit partitioning, Proceedings of the 33rd annual conference on Design automation, p.100-105, June 03-07, 1996, Las Vegas, Nevada, United States
	Shantanu Dutt , Wenyong Deng, VLSI circuit partitioning by cluster-removal using iterative improvement techniques, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.194-200, November 10-14, 1996, San Jose, California, United States
	Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States
	Sachin B. Patkar , H. Narayanan, Improving graph partitions using submodular functions, Discrete Applied Mathematics, v.131 n.2, p.535-553, 12 September 2003
	Mirela Ben-Chen , Craig Gotsman, On the optimality of spectral compression of mesh data, ACM Transactions on Graphics (TOG), v.24 n.1, p.60-80, January 2005
	Nestor F. Michelena , Panos Y. Papalambros, A Hypergraph Framework for Optimal Model-Based Decomposition ofDesign Problems, Computational Optimization and Applications, v.8 n.2, p.173-196, Sept 1997
	Jacob G. Martin, Spectral techniques for graph bisection in genetic algorithms, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
	Byoung-Ki Jeon , Yun-Beom Jung , Ki-Sang Hong, Image segmentation by unsupervised sparse clustering, Pattern Recognition Letters, v.27 n.14, p.1650-1664, 15 October 2006
	Robert Jenssen , Deniz Erdogmus , Kenneth E. Hild, II , Jose C. Principe , Torbjørn Eltoft, Information cut for clustering using a gradient descent approach, Pattern Recognition, v.40 n.3, p.796-806, March, 2007
	Desmond J. Higham , Gabriela Kalna , Milla Kibble, Spectral clustering and its use in bioinformatics, Journal of Computational and Applied Mathematics, v.204 n.1, p.25-37, July, 2007
	Kweku-Muata Osei-Bryson , Tasha R. Inniss, A hybrid clustering algorithm, Computers and Operations Research, v.34 n.11, p.3255-3269, November, 2007
	K. S. Seong , C. M. Kyung, Two-way partitioning based on direction vector, Proceedings of the 1997 European conference on Design and Test, p.306, March 17-20, 1997
	Hyun Soo Kim , Han Kyun Choi , Kwan H. Lee, Feature detection of triangular meshes based on tensor voting theory, Computer-Aided Design, v.41 n.1, p.47-58, January, 2009
	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
	Gabriela Kalna , J. Keith Vass , Desmond J. Higham, Multidimensional partitioning and bi-partitioning: analysis and application to gene expression data sets, International Journal of Computer Mathematics, v.85 n.3-4, p.475-485, March 2008