A New Coarsening Strategy for Multilevel Graph Partitioning

Lu  Yao; Zheng Hua Wang; Wei Cao; Zong Zhe Li

doi:10.4028/www.scientific.net/AMR.490-495.504

Paper Titles

Remote Improved Inspecting Gas Sensing System Based on CAN Communication
p.486

Reliability Index Assignment and Application of Small-Caliber Ammunition
p.490

Precision Analysis for the 3-PRS Parallel Robot
p.495

Study on a Novel MEMS High G Acceleration Sensor
p.499

A New Coarsening Strategy for Multilevel Graph Partitioning
p.504

Research on Electromagnetic Catapult-Oriented Permanent Magnet Linear Synchronous Motor
p.509

Scheme Design and Experimental Verification of Gas Sub-Line Measurement
p.514

Real-Time Implementation AMR-WB Algorithm in TMS320VC5509A DSP
p.519

Research on Methodology of Evolutionary Computing
p.524

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 490-495A New Coarsening Strategy for Multilevel Graph...

A New Coarsening Strategy for Multilevel Graph Partitioning

Abstract:

When applying multilevel scheme to solve the graph partitioning problem, shortcomings and limitations exist in the state-of-the-art coarsening schemes depend mainly on finding maximal matchings to obtain the coarse graphs, which can cause the multilevel algorithms to produce poor-quality solutions. This paper proposes an improved coarsening scheme by improving vertex combining strategy and edge ordering criteria. The new coarsening scheme is more effective in quality, which is proved by both theoretical analysis and experimental results.

You might also be interested in these eBooks

Mechatronics and Intelligent Materials II

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 490-495)

Pages:

504-508

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.490-495.504

Citation:

Cite this paper

Online since:

March 2012

Authors:

Lu Yao, Zheng Hua Wang, Wei Cao, Zong Zhe Li

Keywords:

Graph Partitioning, Maximal Matching, Multilevel Algorithm

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] B.W. Kernighan and S. Lin: The Bell System Technology Journal Vol. 8 (1970), p.291.

Google Scholar

[2] J. Gilbert, G. Miller and S. Teng: Parallel Processing Symposium (1995), p.418.

Google Scholar

[3] T.N. Bui and B. Moon: IEEE Transactions on Computers Vol. 45 (1996), p.841.

Google Scholar

[4] G. Karypis and V. Kumar: Journal of Parallel and Distributed Computing Vol. 48 (1998), p.96.

Google Scholar

[5] A. Pothen, H.D. Simon and K.P. Liu: SIAM Journal on Matrix Analysis and Applications Vol. 11 (1990), p.430.

Google Scholar

[6] H. Gabow: Proceeding of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (1990), p.434.

Google Scholar

[7] B. Monien, R. Preis and R. Diekmann: Quality matching and local improvement for multilevel graph partitioning (Technical report, University of Paderborn 1999).

DOI: 10.1016/s0167-8191(00)00049-1

Google Scholar

[8] B. Hendrickson and R. Leland: A multilevel algorithm for partitioning graphs (Technical report, Sandia National Laboratories 1993).

Google Scholar