A Multilevel Hypergraph Partitioning Algorithm Based on Simulated Annealing

Yao Yuan Zeng; Wen Tao Zhao; Zheng Hua Wang

doi:10.4028/www.scientific.net/AMR.753-755.2908

Paper Titles

Bayesian Estimations of Mixed Exponential Distribution with Type-I Censored Data
p.2887

Web Service Composition Verification of Safety Properties: An Approach Based on Predicate Abstraction
p.2892

A Hybrid Hypergraph Partitioning Algorithm for Scientific Computing
p.2900

Reliability Analysis for Link Mechanism under Influence of Multiple Factors Based on Support Vector Machine
p.2904

A Multilevel Hypergraph Partitioning Algorithm Based on Simulated Annealing
p.2908

An Out-of-Core Method for CFD Simulation in Heterogeneous Environment
p.2912

Determination of Occurrence Grades for Factors Affecting Congelation Failure on Basis of Fuzzy Comprehensive Assessment Method
p.2916

A Mapping Framework between Design Information and Energy Information
p.2920

Adaptive Genetic Algorithm for Hybrid Flow-Shop Scheduling
p.2925

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 753-755A Multilevel Hypergraph Partitioning Algorithm...

A Multilevel Hypergraph Partitioning Algorithm Based on Simulated Annealing

Abstract:

Multilevel hypergraph partitioning is a significant and extensively researched problem in combinatorial optimization. In this paper, we present a multilevel hypergraph partitioning algorithm based on simulated annealing approach for global optimization. Experiments on the benchmark suite of several unstructured meshes show that, for 2-, 4-, 8-, 16-and 32-way partitioning, although more running time was demanded, the quality of partition produced by our algorithm are on the average 14% and the maximum 22% better than those produced by partitioning software hMETIS in term of the SOED metric.

You might also be interested in these eBooks

Materials Processing and Manufacturing III

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 753-755)

Pages:

2908-2911

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.753-755.2908

Citation:

Cite this paper

Online since:

August 2013

Authors:

Yao Yuan Zeng*, Wen Tao Zhao, Zheng Hua Wang

Keywords:

Hypergraph Partitioning, Local Optimization, Multilevel Approach, Partition Quality, Simulated Annealing (SA)

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] S. Roy, S.S. Sarma, and S. Das. INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY 3 (2012), pp.493-499.

Google Scholar

[2] E. Kayaaslan, A. Pinar, U. Catalyürek, and C. Aykanat. SIAM Journal on Scientific Computing 34 (2012), p. A970-A992.

DOI: 10.1137/100810022

Google Scholar

[3] M. Wieling, and J. Nerbonne. Computer Speech & Language 25 (2011), pp.700-715.

Google Scholar

[4] K.D. Devine, E.G. Boman, R.T. Heaphy, B.A. Hendrickson, J.D. Teresco, J. Faik, J.E. Flaherty, and L.G. Gervasio,. Applied Numerical Mathematics 52 (2005), pp.133-152.

DOI: 10.1016/j.apnum.2004.08.028

Google Scholar

[5] Y. Ma, G. Tan, and W. Wang. International Journal of Parallel, Emergent and Distributed Systems 27 (2012), pp.337-346.

Google Scholar

[6] U.V. Catalyurek, D. Bozdag, E.G. Boman, K.D. Devine, R. Heaphy, and L.A. Riesen. Advanced Computational Infrastructures for Parallel and Distributed Applications 66 (2010), p.313.

DOI: 10.1002/9780470558027.ch15

Google Scholar

[7] A.J. Pal, B. Ray, N. Zakaria, and S.S. Sarma. Procedia Computer Science 9 (2012), pp.321-327.

Google Scholar

[8] S. Rital. Fundamenta Informaticae 96 (2009), pp.153-179.

Google Scholar

[9] Information on http: /turbmodels. larc. nasa. gov.

Google Scholar

[10] G. Karypis, and V. Kumar, hMETIS 1. 5: A hypergraph partitioning package, Technical report, Department of Computer Science, University of Minnesota, (1998).

Google Scholar