Article

Free access

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

Authors:

Thang Nguyen Bui,

Byung Ro MoonAuthors Info & Claims

DAC '94: Proceedings of the 31st annual Design Automation Conference

Pages 664 - 669

https://doi.org/10.1145/196244.196607

Published: 06 June 1994 Publication History

PDF eReader

References

[1]

C. Alpert and A. Kahng, "Geometric Embeddings %r Faster and Better Multi-Way Netlist Partitioning," Proc. of the 30th Design Automation Conference, June 1993, pp. 743 748.

Digital Library

Google Scholar

[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.

Google Scholar

[3]

T. N. Bui, S. Chaudhuri, F. T. beighton, and M. Sipser, "Graph Bisection Algorithms with Good Average Case Behavior," Combinatorica, 7(2), 1987, pp. 171 191.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[6]

T. N. Bui and B. R. Moon, "Hyperplane Synthesis for Genetic Algorithms," Proc. of the Fifth International Conference on Genetic Algorithms, July 1993, pp. 102 109.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[9]

P. Chan, M. Schlag, and J. Zien, "Spectral K-Way Ratio-Cut Partitioning and Clustering," Proc. of the 30th Design Automation Conference, June 1993, pp. 549 754.

Digital Library

Google Scholar

[10]

C. Cheng and Y. Wei, "An Improved Two-Way Partitioning Algorithm with Stable Performance," IEEE Trans. CAD, 10(12), Dec. 1991.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[13]

J. Cong and M. Smith, "A Parallel Bottom-up Clustering Algorithm with Applications to Circuit Partitioning in VLSI Circuit Design," Proc. of the 30th Design Automation Conference, June 1993, pp. 755 760.

Digital Library

Google Scholar

[14]

K. DeJong, Analysis of the behavio~" of a Class of Genetic Adaptive Systems, Ph.D. Thesis, University of Michigan, Ann Arbor, 1975.

Google Scholar

[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.

Google Scholar

[16]

C. Fiduccia and R. Mattheyses, "A Linear Time Heuristics for Improving Network Partitions," Proc. of the 19th Design Automation Conference, Jan. 1982, pp. 175 181.

Digital Library

Google Scholar

[17]

D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

Digital Library

Google Scholar

[18]

J. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.

Digital Library

Google Scholar

[19]

L. Hagen and A. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering," IEEE Trans. CAD, 11(9), Sept. 1992.

Digital Library

Google Scholar

[20]

D. Johnson, C. Aragon, L. McGeoch, and C. Schevon, "Optimization by Simulated Annealing: An Experimental Evaluation, Part 1, Graph Partitioning," Operations Research, 37, 1989, pp. 865 892.

Digital Library

Google Scholar

[21]

B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Systems Technical Journal, Vol. 49, Feb. 1970, pp. 291 307.

Crossref

Google Scholar

[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.

Google Scholar

[23]

A. Pothen, H. Simon, and K. Liou, "Partitioning Sparse Matrices with Eigenvectors of Graphs," Siam J. Matrix Anal. App1., 11(3), July 1990, pp. 430 452.

Digital Library

Google Scholar

[24]

D. Schweikert and B. Kernighan, "A Proper Model for Partitioning of Electrical Circuits," Proc. of the 9th Design Automation Workshop, 1972, pp. 57 62.

Digital Library

Google Scholar

[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.

Google Scholar

[26]

Y. Wei and C. Cheng, "Ratio Cut Partitioning for Hierarchical Designs," IEEE Trans. CAD, 10(7), July 1991, pp. 911 921.

Digital Library

Google Scholar

Cited By

View all

Farooq UMehrez H(2021)Pre-Silicon Verification Using Multi-FPGA Platforms: A ReviewJournal of Electronic Testing10.1007/s10836-021-05929-1Online publication date: 23-Feb-2021
https://doi.org/10.1007/s10836-021-05929-1
Andre RSchlag SSchulz CTakadama K(2018)Memetic multilevel hypergraph partitioningProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205475(347-354)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205475
Maity DSaha IMaulik UPlewczynski D(2014)Soft Computing Approach for VLSI Mincut Partitioning: The State of the ArtsProceedings of the Second International Conference on Soft Computing for Problem Solving (SocProS 2012), December 28-30, 201210.1007/978-81-322-1602-5_95(895-903)Online publication date: 26-Feb-2014
https://doi.org/10.1007/978-81-322-1602-5_95
Show More Cited By

Index Terms

A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs
1. Hardware
  1. Integrated circuits
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
      1. Paths and connectivity problems
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

Spectral K-way ratio-cut partitioning and clustering

Recent research on partitioning has focused on the ratio-cut cost metric, which maintains a balance between the cost of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral ...
Partitioning 3-uniform hypergraphs

Bollobas and Thomason conjectured that the vertices of any r-uniform hypergraph with m edges can be partitioned into r sets so that each set meets at least rm/(2r-1) edges. For r=3, Bollobas, Reed and Thomason proved the lower bound (1-1/e)m/3~0.21m, ...
A hybrid genetic search for multi-way graph partitioning based on direct partitioning
GECCO'01: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation

Multi-way partitioning is an important extension of two-way partitioning as it provides a natural and direct model for many partitioning applications. In this paper, we propose a hybrid genetic algorithm for k-way partitioning. The algorithm includes an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '94: Proceedings of the 31st annual Design Automation Conference

June 1994

739 pages

ISBN:0897916530

DOI:10.1145/196244

Chairman:
Michael Lorenzetti
Mentor Graphics Corp., Wilsonville, OR

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC94

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC94: The 31st ACM/IEEE-CAS/EDAC Design Automation Conference

June 6 - 10, 1994

California, San Diego, USA

Acceptance Rates

DAC '94 Paper Acceptance Rate 100 of 260 submissions, 38%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
685
Total Downloads

Downloads (Last 12 months)233
Downloads (Last 6 weeks)38

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Farooq UMehrez H(2021)Pre-Silicon Verification Using Multi-FPGA Platforms: A ReviewJournal of Electronic Testing10.1007/s10836-021-05929-1Online publication date: 23-Feb-2021
https://doi.org/10.1007/s10836-021-05929-1
Andre RSchlag SSchulz CTakadama K(2018)Memetic multilevel hypergraph partitioningProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205475(347-354)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205475
Maity DSaha IMaulik UPlewczynski D(2014)Soft Computing Approach for VLSI Mincut Partitioning: The State of the ArtsProceedings of the Second International Conference on Soft Computing for Problem Solving (SocProS 2012), December 28-30, 201210.1007/978-81-322-1602-5_95(895-903)Online publication date: 26-Feb-2014
https://doi.org/10.1007/978-81-322-1602-5_95
Armstrong EGrewal GAreibi SDarlington G(2010)An investigation of parallel memetic algorithms for VLSI circuit partitioning on multi-core computersCCECE 201010.1109/CCECE.2010.5575207(1-6)Online publication date: May-2010
https://doi.org/10.1109/CCECE.2010.5575207
Shuiping LXiaoxue W(2010)A global method for the limited K‐partitioning of hypergraphs representing optimal design problems in complex machine systemsKybernetes10.1108/0368492101104675339:6(980-989)Online publication date: 15-Jun-2010
https://doi.org/10.1108/03684921011046753
Shih-Pang Tseng Tsai CChiang MYang C(2008)Fast genetic algorithm based on pattern reduction2008 IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.2008.4811277(214-219)Online publication date: Oct-2008
https://doi.org/10.1109/ICSMC.2008.4811277
Alpert CHuang JKahng A(2006)Multilevel circuit partitioningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.71209817:8(655-667)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.712098
Bui TMoon B(2006)GRCAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.70071817:3(193-204)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.700718
Lienig JCohoon J(2005)Genetic algorithms applied to the physical design of VLSI circuits: A surveyParallel Problem Solving from Nature — PPSN IV10.1007/3-540-61723-X_1047(839-848)Online publication date: 11-Jul-2005
https://doi.org/10.1007/3-540-61723-X_1047
Bui TMoon B(2005)Analyzing hyperplane synthesis in genetic algorithms using clustered schemataParallel Problem Solving from Nature — PPSN III10.1007/3-540-58484-6_255(108-118)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58484-6_255
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Spectral K-way ratio-cut partitioning and clustering

Partitioning 3-uniform hypergraphs

A hybrid genetic search for multi-way graph partitioning based on direct partitioning