{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:15:50Z","timestamp":1760242550904,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,10,10]],"date-time":"2017-10-10T00:00:00Z","timestamp":1507593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Open Project of Shandong Provincial Key Laboratory of Computer Networks","award":["SDKLCN-2015-03"],"award-info":[{"award-number":["SDKLCN-2015-03"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A graph is a very important structure to describe many applications in the real world. In many applications, such as dependency graphs and debt graphs, it is an important problem to find and remove cycles to make these graphs be cycle-free. The common algorithm often leads to an out-of-memory exception in commodity personal computer, and it cannot leverage the advantage of multicore computers. This paper introduces a new problem, cycle detection and removal with vertex priority. It proposes a multithreading iterative algorithm to solve this problem for large-scale graphs on personal computers. The algorithm includes three main steps: simplification to decrease the scale of graph, calculation of strongly connected components, and cycle detection and removal according to a pre-defined priority in parallel. This algorithm avoids the out-of-memory exception by simplification and iteration, and it leverages the advantage of multicore computers by multithreading parallelism. Five different versions of the proposed algorithm are compared by experiments, and the results show that the parallel iterative algorithm outperforms the others, and simplification can effectively improve the algorithm's performance.<\/jats:p>","DOI":"10.3390\/a10040115","type":"journal-article","created":{"date-parts":[[2017,10,10]],"date-time":"2017-10-10T10:34:29Z","timestamp":1507631669000},"page":"115","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9251-680X","authenticated-orcid":false,"given":"Huanqing","family":"Cui","sequence":"first","affiliation":[{"name":"College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao 266510, China"},{"name":"Shandong Provincial Key Laboratory of Computer Networks, Shandong Computer Science Center (National Supercomputer Center in Jinan), Jinan 250101, China"},{"name":"Shandong Province Key Laboratory of Wisdom Mine Information Technology, Shandong University of Science and Technology, Qingdao 266510, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Niu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao 266510, China"},{"name":"Shandong Provincial Key Laboratory of Computer Networks, Shandong Computer Science Center (National Supercomputer Center in Jinan), Jinan 250101, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuanai","family":"Zhou","sequence":"additional","affiliation":[{"name":"Business School, Qingdao Binhai College, Qingdao 266555, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minglei","family":"Shu","sequence":"additional","affiliation":[{"name":"Shandong Provincial Key Laboratory of Computer Networks, Shandong Computer Science Center (National Supercomputer Center in Jinan), Jinan 250101, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,10,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1016\/j.ejc.2011.09.030","article-title":"A survey on hamilton cycles in directed graphs","volume":"33","author":"Osthus","year":"2012","journal-title":"Eur. J. Combin."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1109\/TLA.2016.7437229","article-title":"A new algorithm for finding all tours and hamiltonian circuits in graphs","volume":"14","author":"Silva","year":"2016","journal-title":"IEEE Lat. Am. Trans."},{"key":"ref_3","unstructured":"Lv, X., and Zhu, D. (2010, January 24\u201326). An approximation algorithm for the shortest cycle in an undirected unweighted graph. Proceedings of the International Conference on Computer, Mechatronics, Control and Electronic Engineering, Changchun, China."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.1016\/j.ipl.2011.07.019","article-title":"A shortest cycle for each vertex of a graph","volume":"111","author":"Yuster","year":"2011","journal-title":"Inform. Process. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"179","DOI":"10.7151\/dmgt.1354","article-title":"Cycles through specified vertices in triangle-free graphs","volume":"27","author":"Paulusma","year":"2007","journal-title":"Discuss. Math. Gr. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"383","DOI":"10.7151\/dmgt.1863","article-title":"Heavy subgraph conditions for longest cycles to be heavy in graphs","volume":"36","author":"Li","year":"2016","journal-title":"Discuss. Math. Gr. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"363","DOI":"10.7151\/dmgt.1861","article-title":"Large degree vertices in longest cycles of graphs, I","volume":"36","author":"Li","year":"2016","journal-title":"Discuss. Math. Gr. Theory"},{"key":"ref_8","unstructured":"Gerbner, D., Keszegh, B., Palmer, C., and Patkos, B. (2017, October 09). On the Number of Cycles in a Graph with Restricted Cycle Lengths. Available online: https:\/\/arxiv.org\/abs\/1610.03476."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Sankar, K.A., and Sarad, V. (2007, January 25\u201328). A time and memory efficient way to enumerate cycles in a graph. Proceedings of the International Conference on Intelligent and Advanced Systems, Kuala Lumpur, Malaysia.","DOI":"10.1109\/ICIAS.2007.4658438"},{"key":"ref_10","unstructured":"Haeupler, B., Kavitha, T., Mathew, R., Sen, S., and Tarjan, R.E. (2017, October 09). Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance. Available online: https:\/\/arxiv.org\/abs\/1105.2397."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fineman, J.T., Gilbert, S., and Tarjan, R.E. (2016). A new approach to incremental cycle detection and related problems. ACM Trans. Algorithms, 12.","DOI":"10.1145\/2756553"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","article-title":"Depth-first search is inherently sequential","volume":"20","author":"Reif","year":"1985","journal-title":"Inform. Process. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1109\/TCOMM.2012.100912.120503","article-title":"Message-passing algorithms for counting short cycles in a graph","volume":"61","author":"Karimi","year":"2013","journal-title":"IEEE Trans. Commun."},{"key":"ref_14","unstructured":"Rocha, R.C., and Thatte, B.D. (2015, January 25\u201328). Distributed cycle detection in large-scale sparse graphs. Proceedings of the Simp\u00f3sio Brasileiro de Pesquisa Operacional, Pernambuco, Brazil."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., and Czajkowski, G. (2010, January 6\u201311). Pregel: A system for large-scale graph processing. Proceedings of the ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA.","DOI":"10.1145\/1807167.1807184"},{"key":"ref_16","unstructured":"Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., and Stoica, I. (2014, January 6\u20138). GraphX: Graph processing in a distributed dataflow framework. Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation, Broomfield, CO, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Salihoglu, S., and Widom, J. (2013, January 29\u201331). GPS: A graph processing system. Proceedings of the 25th International Conference on Scientific and Statistical Database Management, Baltimore, MD, USA.","DOI":"10.1145\/2484838.2484843"},{"key":"ref_18","unstructured":"F\u00e9ray, V. (2017, October 09). Weighted dependency graphs. Available online: https:\/\/arxiv.org\/abs\/1605.03836."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1016\/j.jpdc.2005.03.007","article-title":"Finding strongly connected components in distributed graphs","volume":"65","author":"McLendon","year":"2005","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Leskovec, J., and Sosic, R. (2016). SNAP: A general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol., 8.","DOI":"10.1145\/2898361"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Seidl, T., Boden, B., and Fries, S. (2012, January 24\u201328). CC-MR\u2014Finding connected components in huge graphs with MapReduce. Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Bristol, UK.","DOI":"10.1007\/978-3-642-33460-3_35"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Slota, G.M., Rajamanickam, S., and Madduri, K. (2014, January 19\u201323). BFS and coloring-based parallel algorithms for strongly connected components and related problems. Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA.","DOI":"10.1109\/IPDPS.2014.64"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/115\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:46:53Z","timestamp":1760208413000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,10]]},"references-count":22,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,12]]}},"alternative-id":["a10040115"],"URL":"https:\/\/doi.org\/10.3390\/a10040115","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2017,10,10]]}}}