정련법을 이용한 하이퍼그래프 분할 = Hypergraph Partitioning By Using Reodered Simulated-anealing

다국어 초록 (Multilingual Abstract)

In this paper we present a reodered simulated-anealing algorithm which is capable of applying odering based k-way partitioned clusters. This method is used for improvement of the objectives of partitioning which are k-way partitioned by using odering algorithm. It changes the positions of the clusters and the vertices in each clusters. Reodered vertices are splitted by using DP-RP method and this process has an opportunity to improve the objective functions. This algorithm has advantages to improve the quality of the solutions for various purposes. Experimental results on several graphs demonstrate that proposed algorithm provides substantial enhancement.

참고문헌 (Reference)

1 김재진, "제한조건을 고려한 효율적 회로 설계 알고리즘" (사)디지털산업정보학회 8 (8): 41-46, 2012

2 D. J. H. Huang, "When Clusters Meet Partitions: New Density-Based Methods for Circuit Decomposition" 60-64, 1995

3 Y. C. Wei, "Towards Efficient Hierarchical Designs by Ratio Cut Partitioning" 298-301, 1989

4 P. K. Chan, "Spectral K-way Ratio-Cut Partitioning and Clustering" 13 (13): 1088-1096, 1994

5 S. J. Kim, "Reordering Algorighm for Hypergraph Partitioning" Kyungpook National University 2000

6 S. Dutt, "Probability-Based Approaches to VLSI Curcuit Partitioning" 19 (19): 534-549, 2000

7 R. Rajaraman, "Optimal clustering for delay minimization" 309-314, 1993

8 J. Cong, "Net Partitions Yield Better Module Partitions" 47-52, 1992

9 C. J. Alpert., "Multi-way Graph and Hypergraph Partitioning" UCLA 1996

10 C. J. Alpert, "Multi-Way Partitioning Via Space-filling Curves and Dynamic Programming" 652-657, 1994

11 N. Selvakkumaran, "Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization" 25 (25): 504-517, 2006

12 최현준, "FPGA를 이용한 디지털 계측 시스템의 설계 및 구현" (사)디지털산업정보학회 9 (9): 55-61, 2013

13 W. Son, "Efficient and Effective Placements for Very Large Circuits" 170-177, 1993

14 H. Nagamochi, "Computing Edge-Connectivity in Multigraphs and Capacitated Graphs" 5 (5): 54-66, 1992

15 C. W. Yeh, "A Probabilistic Multi-Commodity Flow Solution to Circuit Clustering Problems" 428-431, 1992

16 C. J. Alpert, "A General Framework for Vertex Orderings, With Application to Circuit Clustering" 4 (4): 240-246, 1996