{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T23:30:40Z","timestamp":1764977440225,"version":"3.46.0"},"reference-count":20,"publisher":"Walter de Gruyter GmbH","issue":"3","license":[{"start":{"date-parts":[[2016,4,19]],"date-time":"2016-04-19T00:00:00Z","timestamp":1461024000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,7,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The formal description of weighted hypergraph partitioning problem is presented. We describe the solution of the weighted hypergraph partitioning problem based on the multi-level method. We propose the multi-level discrete particle swarm optimization refinement algorithm, whose each particle\u2019s position in |V|-dimensional can be considered as the corresponded partitioning. During the refinement process of the uncoarsening phase, the algorithm projects successively each particle\u2019s corresponded partitioning back to the next-level finer hypergraph, and the degree of particle\u2019s freedom increases with the increase in solution space\u2019s dimension. The algorithm also regards the gain of vertex as particle information for the heuristic search and successfully searches the solution space based on the intelligent behavior between individuals\u2019 collaboration. Furthermore, the improved compressed storage format of weighted hypergraph is presented and the two-dimensional auxiliary array is designed for counting the vertices of each hypergraph in different partitions. The rapid method of calculating the vertex\u2019s gain and the cut\u2019s size are proposed to avoid traversing each vertex of hyperedge and reduce the algorithm\u2019s time complexity and space complexity. Experimental results show that the algorithm not only can find the better partitioning of weighted hypergraph than the move-based method but also can improve the search capability of the refinement algorithm.<\/jats:p>","DOI":"10.1515\/jisys-2015-0058","type":"journal-article","created":{"date-parts":[[2016,4,19]],"date-time":"2016-04-19T13:20:24Z","timestamp":1461072024000},"page":"407-420","source":"Crossref","is-referenced-by-count":0,"title":["Multi-Level Refinement Algorithm of Weighted Hypergraph Partitioning Problem"],"prefix":"10.1515","volume":"26","author":[{"given":"Ming","family":"Leng","sequence":"first","affiliation":[{"name":"Key Laboratory of Watershed Ecology and Geographical Environment Monitoring of NASG , Jinggangshan University , Ji\u2019an , Jiangxi , China"}]},{"given":"Ling-yu","family":"Sun","sequence":"additional","affiliation":[{"name":"Key Laboratory of Watershed Ecology and Geographical Environment Monitoring of NASG , Jinggangshan University , Ji\u2019an , Jiangxi , China"}]},{"given":"Kai-qiang","family":"Guo","sequence":"additional","affiliation":[{"name":"Key Laboratory of Watershed Ecology and Geographical Environment Monitoring of NASG , Jinggangshan University , Ji\u2019an , Jiangxi , China"}]}],"member":"374","published-online":{"date-parts":[[2016,4,19]]},"reference":[{"key":"2025120523272175789_j_jisys-2015-0058_ref_001_w2aab3b7d101b1b6b1ab2b1b1Aa","doi-asserted-by":"crossref","unstructured":"C. J. Alpert, The ISPD98 Circuit Benchmark Suite, in: Proceedings of ACM International Symposium of Physical Design, pp. 80\u201385, ACM Press, New York, USA, 1998.","DOI":"10.1145\/274535.274546"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_002_w2aab3b7d101b1b6b1ab2b1b2Aa","doi-asserted-by":"crossref","unstructured":"C. J. Alpert and A. B. Kahng, Recent directions in netlist partitioning, integration. VLSI J.19 (1995), 1\u201381.","DOI":"10.1016\/0167-9260(95)00008-4"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_003_w2aab3b7d101b1b6b1ab2b1b3Aa","unstructured":"J. Dongarra, G. Fox and K. Kennedy, Sourcebook of parallel computering, Morgan Kaufmann Publishers, San Francisco, 2003."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_004_w2aab3b7d101b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"C. Fiduccia and R. Mattheyses, A linear-time heuristics for improving network partitions, in: Proceedings of the 19th Design Automation Conference, pp. 175\u2013181, IEEE Computer Society Press, Los Alamitos, USA, 1982.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_005_w2aab3b7d101b1b6b1ab2b1b5Aa","doi-asserted-by":"crossref","unstructured":"L. Hagen, D. Huang and A. Kahng, On implementation choices for iterative improvement partitioning algorithms, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst.16 (1997), 1199\u20131205.","DOI":"10.1109\/43.662682"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_006_w2aab3b7d101b1b6b1ab2b1b6Aa","doi-asserted-by":"crossref","unstructured":"G. Karypis, R. Aggarwal and V. Kumar, Multilevel hypergraph partitioning: applications in VLSI domain, in: Proceedings of 34th Design Automation Conference, pp. 271\u2013283, ACM Press, New York, USA, 1998.","DOI":"10.1145\/266021.266273"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_007_w2aab3b7d101b1b6b1ab2b1b7Aa","doi-asserted-by":"crossref","unstructured":"G. Karypis, R. Aggarwal and V. Kumar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Transactions on VLSI Syst.7 (1999), 69\u201379.","DOI":"10.1109\/92.748202"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_008_w2aab3b7d101b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J49 (1970), 291\u2013307.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_009_w2aab3b7d101b1b6b1ab2b1b9Aa","unstructured":"M. Leng, L.Y. Sun and S.N. Yu, Spectral-based weighted undirected graph partitioning algorithm, Appl. Res. Comput.26 (2009), 2086\u20132089 (in Chinese)."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_010_w2aab3b7d101b1b6b1ab2b1c10Aa","unstructured":"M. Leng, L.Y. Sun, J.N. Bian, Y.C. Ma and P. Zhu, Research on cellular automata model of hypergraph partitioning problem and its algorithm, Comput. Eng.38 (2012), 23\u201327 (in Chinese)."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_011_w2aab3b7d101b1b6b1ab2b1c11Aa","unstructured":"M. Leng, L.Y. Sun, K.Q. Guo and P. Zhu, An effective converter to translate VLSI design into weighted hypergraph, Microelectron. Comput.29 (2012), 7\u201313 (in Chinese)."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_012_w2aab3b7d101b1b6b1ab2b1c12Aa","unstructured":"M. Leng, L.Y. Sun, P. Zhu, J.N. Bian and Y.C. Ma, Comparative experiment of the core property of weighted hypergraph based on the various matching strategies, Comput. Eng.39 (2013), 85\u201390 (in Chinese)."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_013_w2aab3b7d101b1b6b1ab2b1c13Aa","doi-asserted-by":"crossref","unstructured":"T. Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley and Sons Co, New York, 1990.","DOI":"10.1007\/978-3-322-92106-2"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_014_w2aab3b7d101b1b6b1ab2b1c14Aa","doi-asserted-by":"crossref","unstructured":"E. Montagn and A. Ekambaram, An optimal storage format for sparse matrices, Inf. Process Lett.90 (2004), 87\u201392.","DOI":"10.1016\/j.ipl.2004.01.014"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_015_w2aab3b7d101b1b6b1ab2b1c15Aa","unstructured":"G.F. Nan, Research on algorithm solving key problem in VLSI physical design, Ph.D. Dissertation, Tianjing University, 2004 (in Chinese)."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_016_w2aab3b7d101b1b6b1ab2b1c16Aa","unstructured":"F. Pellegrini, Scotch 5.1 User\u0105\u0155s guide. Technical report, LaBRI, University Bordeaux I, August 2008. Available from http:\/\/www.labri.fr\/pelegrin\/scotch\/."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_017_w2aab3b7d101b1b6b1ab2b1c17Aa","doi-asserted-by":"crossref","unstructured":"F. Pellegrini and J. Roman, Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs, in: Proceedings of the HPCN\u201996, pp. 493\u2013498, LNCS 1067, Brussels, 1996.","DOI":"10.1007\/3-540-61142-8_588"},{"key":"2025120523272175789_j_jisys-2015-0058_ref_018_w2aab3b7d101b1b6b1ab2b1c18Aa","unstructured":"J. Pilkington, Partitioning with space filling curves, Ph.D. Dissertation, University of California, 1994."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_019_w2aab3b7d101b1b6b1ab2b1c19Aa","unstructured":"H. L. Shi, Research on job scheduling on cloud computing, Ph.D. Dissertation, Nanjing University of Science and Technology, 2012 (in Chinese)."},{"key":"2025120523272175789_j_jisys-2015-0058_ref_020_w2aab3b7d101b1b6b1ab2b1c20Aa","doi-asserted-by":"crossref","unstructured":"R. Soufiane, Hypergraph cuts and unsupervised representation for image segmentation, Fundam. Inform.96 (2009), 153\u2013179.","DOI":"10.3233\/FI-2009-172"}],"container-title":["Journal of Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jisys\/26\/3\/article-p407.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jisys-2015-0058\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jisys-2015-0058\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T23:27:36Z","timestamp":1764977256000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jisys-2015-0058\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,19]]},"references-count":20,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,5,11]]},"published-print":{"date-parts":[[2017,7,26]]}},"alternative-id":["10.1515\/jisys-2015-0058"],"URL":"https:\/\/doi.org\/10.1515\/jisys-2015-0058","relation":{},"ISSN":["2191-026X","0334-1860"],"issn-type":[{"type":"electronic","value":"2191-026X"},{"type":"print","value":"0334-1860"}],"subject":[],"published":{"date-parts":[[2016,4,19]]}}}