A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs

Full text

Pdf (218 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 31st annual Design Automation Conference table of contents

San Diego, California, United States

Pages: 664 - 669

Year of Publication: 1994

ISBN:0-89791-653-0

Authors

Thang Nguyen Bui	Dept. of Computer Science, Pennsylvania State University, Middletown, PA
Byung Ro Moon	Dept. of Computer Science and Engineering, Pennsylvania State University, University Park, PA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 4

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/196244.196607 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	J. Bhuyan, V. Raghavan, and V. Elayavalli, "Genetic Algorithm for Clustering with an Ordering Representation," Proc. of the Fourth International Conference on Genetic Algorithms, July 1991, pp. 408 415.
	3	Thang Nguyen Bui , F. Thomson Leighton , Soma Chaudhuri , Michael Sipser, Graph bisection algorithms with good average case behavior, Combinatorica, v.7 n.2, p.171-191, June 1, 1987 [doi>10.1007/BF02579448]
	4	T. N. Bui and C. Jones, "A Heuristic for Reducing Fill-In in Sparse Matrix Factorization," Proc. of the 6th SIAM Conference on Parallel Processing for Scientific Computing, Norfolk, Virginia, March 1993, pp. 445 452.
	5	T. N. Bui and B. R. Moon, "A Genetic Algorithm for a Special Class of the Quadratic Assignment Problem," The Quadratic Assignment and _Related problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, in press.
	6	Thang Nguyen Bui , Byung Ro Moon, Hyperplane Synthesis for Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.102-109, June 01, 1993
	7	T. N. Bui and B. R. Moon, "A New Genetic Approach for The Traveling Salesman Problem," to appear in the Proc. of the IEEE Conference on Evolutionary Computation, July 1994.
	8	T. N. Bui and B. R. Moon, "Analyzing Hyperplane Synthesis in Genetic Algorithms Using Clustered Schemata," Technical Report CS-93-08, Computer Science and Engineering Dept., Pennsylvania State University, University Park, Pa., Apr. 1993, revised in Mar. 1994.
	9	Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, Spectral K-way ratio-cut partitioning and clustering, Proceedings of the 30th international conference on Design automation, p.749-754, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165117]
	10	C. Cheng and Y. Wei, "An Improved Two-Way Partitioning Algorithm with Stable Performance," IEEE Trans. CAD, 10(12), Dec. 1991.
	11	J. Cohoon, W. Martin, and D. Pdchards, "A Multi-population Genetic Algorithm for Solving the K-Partition Problem on Hyper-cubes," Proc. of the Fourth International Conference on Genetic Algorithms, July 1991, pp. 244 248.
	12	R. Collins and D. Jefferson, "Selection in Massively Parallel Genetic Algorithms," Proc. of the Fourth International Conference on Genetic Algorithms, July 1991, pp. 249 256.
	13	Jason Cong , M'Lissa Smith, A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design, Proceedings of the 30th international conference on Design automation, p.755-760, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165119]
	14	K. DeJong, Analysis of the behavio~" of a Class of Genetic Adaptive Systems, Ph.D. Thesis, University of Michigan, Ann Arbor, 1975.
	15	K. DeJong and W. Spears, "A Formal Analysis of The Role of Multi-Point Crossover in Genetic Algorithms," Annals of Math. AI Journal, Vol. 5, 1992, pp. 1 26.
	16	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
	17	David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	18	John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
	19	L. Hagen and A. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering," IEEE Trans. CAD, 11(9), Sept. 1992.
	20	David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning, Operations Research, v.37 n.6, p.865-892, Nov–Dec. 1989 [doi>10.1287/opre.37.6.865]
	21	B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Systems Technical Journal, Vol. 49, Feb. 1970, pp. 291 307.
	22	G. Laszewski, "Intelligent Structural Operators for the k-way Graph Partitioning Problem," Proc. of the Fourth Int. Conf. on Genetic Algorithms, July 1991, pp. 45 52.
	23	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]
	24	D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
	25	Y. Wei and C. Cheng, "Toward Efficient Hierarchical Designs by Ratio Cut Partitioning," Proc. IEEE International Conference on Computer-Aided Design, 1989, pp. 298 301.
	26	Y. Wei and C. Cheng, "Ratio Cut Partitioning for Hierarchical Designs," IEEE Trans. CAD, 10(7), July 1991, pp. 911 921.

CITED BY 4

	Buyng-Ro Moon , Yoon-Sik Lee , Chun-Kyung Kim, Genetic VLSI circuit partitioning with two-dimensional geographic crossover and zigzag mapping, Proceedings of the 1997 ACM symposium on Applied computing, p.274-278, April 1997, San Jose, California, United States
	Scott Hauck , Gaetano Borriello, Logic partition orderings for multi-FPGA systems, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.32-38, February 12-14, 1995, Monterey, California, United States
	James Cohoon , John Karro , Jens Lienig, Evolutionary algorithms for the physical design of VLSI circuits, Advances in evolutionary computing: theory and applications, Springer-Verlag New York, Inc., New York, NY, 2003
	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