Paper Titles

An Image Edge Detection Method Based on Improved Ant Colony Algorithm
p.236

Researches on Design and Implementations of Two 2-Bit Predictors
p.241

Fuzzy Relational Clustering Based on Knowledge Mesh and its Application
p.247

Algorithm for Feature Extraction of Heart Sound Signal Based on Sym7 Wavelet
p.252

Local Refinement for Graph Partitioning Based on Level Structure
p.257

Study on the Algorithm for Real-Time Interpolation of NURBS Curve
p.262

Root Node Vaccines for Bayesian Network Structure Learning Based on Immune Algorithm
p.268

Improving the Performance of Process Controllers Using a New Clustered Neural Network
p.273

The Image Filtering Algorithm Based on the Enlarged Pixel Domain
p.278

HomeAdvanced Engineering ForumAdvanced Engineering Forum Vol. 1Local Refinement for Graph Partitioning Based on...

Local Refinement for Graph Partitioning Based on Level Structure

Article Preview

Abstract:

Graph partitioning is a fundamental problem in several scientific and engineering applications. In this paper, we propose a heuristic local refinement algorithm for graph partitioning, which seeks to improve the quality of separators by reducing the width of the level structure. The experiments reported in this paper show that the use of our local refinement algorithm results in a considerable improvement in the quality of partitions over conventional graph partitioning scheme based on level structure.

By email View Pdf

You have full access to the following eBook

Emerging Engineering Approaches and Applications

Info:

Periodical:

Advanced Engineering Forum (Volume 1)

Pages:

257-261

DOI:

https://doi.org/10.4028/www.scientific.net/AEF.1.257

Citation:

Cite this paper

Online since:

September 2011

Authors:

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

Keywords:

Graph Partition, Level Structure, Local Refinement

Export:

RIS, BibTeX

Permissions:

Creative Commons CC BY 4.0

Share:

Citation:

[1] M.R. Garey, D.S. Johnson, L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science. 1 (1976) 237-267.

DOI: 10.1016/0304-3975(76)90059-1

[2] R.J. Lipton, R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177-189.

DOI: 10.1137/0136016

[3] B.W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphics, The Bell Sys. Tech. Journal. (1970) 291-307.

DOI: 10.1002/j.1538-7305.1970.tb01770.x

[4] C. Fiduccia, R. Mattheyses, A linear time heuristic for improving network partitions, In Proc. 19th IEEE Design Automation Conference. (1982) 175-181.

DOI: 10.1109/dac.1982.1585498

[5] H.D. Simon, S. Teng, How good is recursive bisection, SIAM J. Scientific Computing. 18 (1997) 1436-1445.

DOI: 10.1137/s1064827593255135

[6] J. Gilbert, G. Miller, S. Teng, Geometric mesh partitioning: implementation and experiments, In Proc. 9th Int. Parallel Processing Symposium. (1995) 418-427.

DOI: 10.1109/ipps.1995.395965

[7] G. Karypis, V. Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing. 48 (1998) 96-129.

DOI: 10.1006/jpdc.1997.1404

[8] J. Cong, M. Smith, A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design, In Proc. ACM/IEEE Design Automation Conference. (1993) 755-760.

DOI: 10.1145/157485.165119

[9] A. Pothen, H.D. Simon, K.P. Liu, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. on Matrix Analysis and Applications. 11 (1990) 430-452.

DOI: 10.1137/0611030

[10] H.D. Simon, Partitioning of unstructured problems for parallel processing, Computing Systems in Engineering. 2 (1991) 135-148.

DOI: 10.1016/0956-0521(91)90014-v

[11] D.S. Johnson, C.R. Aragon, L.A. McGeoch, C. Schevon, Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning, Oper. Res. 37 (1989) 865-892.

DOI: 10.1287/opre.37.6.865

[12] E. Rolland, H. Pirkul, F. Glover, Tabu search for graph partitioning, Ann. Oper. Res. 63 (1996) 209-232.

DOI: 10.1007/bf02125455

[13] T.N. Bui, B. Moon, Genetic algorithm and graph partitioning, IEEE Transactions on Computers. 45 (1996) 841-855.

DOI: 10.1109/12.508322

[14] N.E. Gibbs, W.G. Jr. Poole, P.K. Stockmeyer, An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM J. Numer. Anal. 13 (1976) 236-250.

DOI: 10.1137/0713023

[15] Matrix Market on http: /math. nist. gov/MatrixMarket.