{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T03:35:27Z","timestamp":1761708927809,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Inspired by many deadlock detection applications, the feedback vertex set is defined as a set of vertices in an undirected graph, whose removal would result in a graph without cycle. The Feedback Vertex Set Problem, known to be NP-complete, is to search for a feedback vertex set with the minimal cardinality to benefit the deadlock recovery. To address the issue, this paper presents NewkLS FVS(LS, local search; FVS, feedback vertex set), a variable depth-based local search algorithm with a randomized scheme to optimize the efficiency and performance. Experimental simulations are conducted to compare the algorithm with recent metaheuristics, and the computational results show that the proposed algorithm can outperform the other state-of-art algorithms and generate satisfactory solutions for most DIMACSbenchmarks.<\/jats:p>","DOI":"10.3390\/a6040726","type":"journal-article","created":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T12:41:02Z","timestamp":1383309662000},"page":"726-746","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An Efficient Local Search for the Feedback Vertex Set Problem"],"prefix":"10.3390","volume":"6","author":[{"given":"Zhiqiang","family":"Zhang","sequence":"first","affiliation":[{"name":"Key Laboratory of Pattern Recognition and Intelligent Information Processing, Shiling, Institutions of Higher Education of Sichuan Province, Chengdu 610106, China"},{"name":"School of Information Science and Technology, Chengdu University, Chengdu 610106, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ansheng","family":"Ye","sequence":"additional","affiliation":[{"name":"Key Laboratory of Pattern Recognition and Intelligent Information Processing, Shiling, Institutions of Higher Education of Sichuan Province, Chengdu 610106, China"},{"name":"School of Information Science and Technology, Chengdu University, Chengdu 610106, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoqing","family":"Zhou","sequence":"additional","affiliation":[{"name":"Key Laboratory of Pattern Recognition and Intelligent Information Processing, Shiling, Institutions of Higher Education of Sichuan Province, Chengdu 610106, China"},{"name":"School of Information Science and Technology, Chengdu University, Chengdu 610106, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zehui","family":"Shao","sequence":"additional","affiliation":[{"name":"Key Laboratory of Pattern Recognition and Intelligent Information Processing, Shiling, Institutions of Higher Education of Sichuan Province, Chengdu 610106, China"},{"name":"School of Information Science and Technology, Chengdu University, Chengdu 610106, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2013,11,1]]},"reference":[{"key":"ref_1","unstructured":"Silberschatz, A., and Galvin, P. (1994). Operating System Concepts, Addison Wesley. [4th ed.]."},{"key":"ref_2","unstructured":"Nijsssen, G. (1976). Modeling in Data Base Management System, North-Holland."},{"key":"ref_3","unstructured":"Karp, R.M. (1972). Complexity of Computer Computations, Plenum Press."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/j.ipl.2005.05.010","article-title":"An effective local search for the maximum clique problem","volume":"95","author":"Katayama","year":"2005","journal-title":"Inf. Process. Lett."},{"key":"ref_5","unstructured":"Hansen, P. (1986). Congress on Numerical Methods in Combinatorial Optimization."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","article-title":"Tabu search-part I","volume":"1","author":"Glover","year":"1989","journal-title":"ORSA J. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/ijoc.2.1.4","article-title":"Tabu search-part II","volume":"2","author":"Glover","year":"1990","journal-title":"ORSA J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","article-title":"An efficient heuristic procedure for partitioning graphs","volume":"49","author":"Kernighan","year":"1970","journal-title":"Bell Syst. Tech. J."},{"key":"ref_10","unstructured":"Voss, S. (1999). Metaheuristics, Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1016\/S0377-2217(00)00100-4","article-title":"Variable neighborhood search: Principles and applications","volume":"130","author":"Hansen","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","article-title":"Variable neighborhood search","volume":"24","author":"Hansen","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/s004530010074","article-title":"Reactive local search for maximum clique","volume":"29","author":"Battiti","year":"2001","journal-title":"Algorithmica"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.dam.2003.09.012","article-title":"Variable neighborhood search for the maximum clique","volume":"145","author":"Hansen","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02023002","article-title":"Solving the maximum clique problem using a tabu search approach","volume":"41","author":"Gendreau","year":"1993","journal-title":"Ann. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1016\/j.cor.2006.05.014","article-title":"A graph coloring heuristic using partial solutions and a reactive tabu scheme","volume":"35","author":"Zufferey","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-540-71615-0_8","article-title":"Iterated k-opt local search for the maximum clique problem","volume":"4446","author":"Katayama","year":"2007","journal-title":"Lecture Notes Comput. Sci."},{"key":"ref_18","unstructured":"Katayama, K., and Narihisa, H. (, January January). Iterated Local Search Approach Using Genetic Transformation to the Traveling Salesman Problem. Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, Florida, USA."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10878-006-9635-y","article-title":"Phased local search for the maximum clique problem","volume":"12","author":"Pullan","year":"2006","journal-title":"J. Comb. Optim."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","article-title":"Chained Lin\u2013Kernighan for large traveling salesman problems","volume":"15","author":"Applegate","year":"2003","journal-title":"Inf. J. Comput."},{"key":"ref_21","first-page":"446","article-title":"Local Optimization and the Traveling Salesman Problem","volume":"443","author":"Johnson","year":"1990","journal-title":"Automata, Languages and Programming: Lecture Notes in Computer Science"},{"key":"ref_22","first-page":"297","article-title":"Memetic algorithms for the traveling salesman problem","volume":"13","author":"Merz","year":"2001","journal-title":"Complex Syst."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1162\/106365600568103","article-title":"Fitness landscapes, memetic algorithms and greedy operators for graph bipartitioning","volume":"8","author":"Merz","year":"2000","journal-title":"Evol. Comput."},{"key":"ref_24","unstructured":"DIMACS Benchmarks. Available online: http:\/\/mat.gsia.cmu.edu\/COLOR\/instances.html."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/726\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:50:19Z","timestamp":1760219419000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/726"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,1]]},"references-count":25,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12]]}},"alternative-id":["a6040726"],"URL":"https:\/\/doi.org\/10.3390\/a6040726","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,11,1]]}}}