Comparative Experiment of the Core Property of Weighted Hyper-Graph Based on the ISPD98 Benchmark

摘要

Combined with the application of circuit partitioning, the hyper-graph model of ISPD98 benchmark is built on the weighted hyper-graph and the formal description of weighted hyper-graph partitioning problem is presented. The weighted hyper-graph partitioning algorithms based on the multi-level method is described. We also propose the matching strategy based on the core property of vertex which improves previous matching strategies based on the local information of vertex. Furthermore, we extend the core notion of graph to the hyper-graph, propose the core notion of hyper-graph and give its formal description. Finally, we carry out the comparative experiment between the degree and core of vertex based on 18 hyper-graphs of ISPD98 benchmark. The experiment and analysis show the core of vertex can more nearly reflects the importance of vertex in the coarse hyper-graph of each level than the degree of vertex.