{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T17:47:46Z","timestamp":1754156866124,"version":"3.41.2"},"reference-count":47,"publisher":"Emerald","issue":"2","license":[{"start":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T00:00:00Z","timestamp":1739318400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.emerald.com\/insight\/site-policies"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["DTA"],"published-print":{"date-parts":[[2025,4,11]]},"abstract":"<jats:sec><jats:title content-type=\"abstract-subheading\">Purpose<\/jats:title><jats:p>Maximum <jats:italic>k<\/jats:italic> vertex cover problem is a significant combinatorial optimization problem with various applications, such as transportation planning, social networks and sensor placement. Up to now, no practical algorithm has ever been proposed to solve this problem. Therefore, this paper aims to present an efficient local search algorithm LSKVC combining three methods for it.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-subheading\">Design\/methodology\/approach<\/jats:title><jats:p>First, the quick incremental evaluation method is proposed to update the related vertex scores following each addition or removal incrementally rather than recalculating them, which can speed up the algorithm. Second, the configuration checking method forbids vertices whose configuration has not changed since the last removal from being added into the candidate solution again, which can avoid the cycling problem effectively. Third, the two-stage exchange method swaps the pairs of inside and outside vertices separately rather than simultaneously, which can guarantee the tradeoff between the accuracy and complexity of the algorithm.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-subheading\">Findings<\/jats:title><jats:p>The proposed algorithm LSKVC is compared with the traditional GRASP algorithm and the well-known commercial solver CPLEX on DIMACS and BHOSLIB benchmarks. For the best solutions, the LSKVC algorithm is significantly superior to GRASP and CPLEX on DIMACS instances and the CPLEX solver fails, and the LSKVC algorithm slightly outperforms GRASP on the BHOSLIB instances. In addition, we undertake comparative studies of the offered methodologies and demonstrate their efficacy.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-subheading\">Originality\/value<\/jats:title><jats:p>In previous research, the focus on the maximum <jats:italic>k<\/jats:italic>-vertex cover problem primarily centered\u00a0around exact algorithms and approximation algorithms, with limited application of heuristic algorithms. While heuristic algorithms have been well-explored for the closely related Minimum Vertex Cover problem, they have seen limited application in the context of the maximum <jats:italic>k<\/jats:italic>-vertex cover problem. Consequently, existing algorithms designed for the Minimum Vertex Cover problem do not exhibit satisfactory performance when applied to the maximum <jats:italic>k<\/jats:italic>-vertex cover problem. In response to this challenge, we have undertaken algorithmic improvements specifically tailored to address this issue.<\/jats:p><\/jats:sec>","DOI":"10.1108\/dta-11-2023-0788","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T07:22:11Z","timestamp":1739258531000},"page":"362-392","source":"Crossref","is-referenced-by-count":0,"title":["An efficient local search algorithm for the maximum <i>k<\/i>-vertex cover problem"],"prefix":"10.1108","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2915-8242","authenticated-orcid":false,"given":"Ruizhi","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0407-6387","authenticated-orcid":false,"given":"Fangzhou","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siqi","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruiqi","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6226-2394","authenticated-orcid":false,"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3073-4219","authenticated-orcid":false,"given":"Shuli","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2025,2,12]]},"reference":[{"key":"key2025041114531997300_ref001","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.eswa.2017.10.023","article-title":"New efficient hybrid candlestick technical analysis model for stock market timing on the basis of the support vector machine and heuristic algorithms of imperialist competition and genetic","volume":"94","year":"2017","journal-title":"Expert Systems with Applications"},{"key":"key2025041114531997300_ref002","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2015.09.023","article-title":"Branch-and-reduce exponential\/fpt algorithms in practice: a case study of vertex cover","volume":"609","year":"2016","journal-title":"Theoretical Computer Science"},{"year":"2020","journal-title":"arXiv preprint arXiv:2012.04883","article-title":"On distributed algorithms for minimum dominating set problem, from theory to application","key":"key2025041114531997300_ref003"},{"issue":"2","key":"key2025041114531997300_ref004","first-page":"218","article-title":"Harnessing genetic algorithm for vertex cover problem","volume":"4","year":"2012","journal-title":"International Journal on Computer Science and Engineering"},{"issue":"3","key":"key2025041114531997300_ref005","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/937503.937505","article-title":"Metaheuristics in combinatorial optimization: overview and conceptual comparison","volume":"35","year":"2003","journal-title":"ACM Computing Surveys"},{"year":"2015","article-title":"Balance between complexity and quality: local search for minimum vertex cover in massive graphs","key":"key2025041114531997300_ref006"},{"key":"key2025041114531997300_ref007","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1609\/aaai.v24i1.7539","article-title":"Ewls: a new local search for minimum vertex cover","year":"2010"},{"issue":"9-10","key":"key2025041114531997300_ref008","doi-asserted-by":"publisher","first-page":"1672","DOI":"10.1016\/j.artint.2011.03.003","article-title":"Local search with edge weighting and configuration checking heuristics for minimum vertex cover","volume":"175","year":"2011","journal-title":"Artificial Intelligence"},{"key":"key2025041114531997300_ref009","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1613\/jair.3907","article-title":"Numvc: an efficient local search algorithm for minimum vertex cover","volume":"46","year":"2013","journal-title":"Journal of Artificial Intelligence Research"},{"key":"key2025041114531997300_ref010","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1613\/jair.5443","article-title":"Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess","volume":"59","year":"2017","journal-title":"Journal of Artificial Intelligence Research"},{"key":"key2025041114531997300_ref011","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.24963\/ijcai.2020\/204","article-title":"Two-goal local search and inference rules for minimum dominating set","year":"2020"},{"issue":"1","key":"key2025041114531997300_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-021-3291-3","article-title":"Toward the minimum vertex cover of complex networks using distributed potential games","volume":"66","year":"2023","journal-title":"Science China Information Sciences"},{"issue":"40-42","key":"key2025041114531997300_ref013","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","article-title":"Improved upper bounds for vertex cover","volume":"411","year":"2010","journal-title":"Theoretical Computer Science"},{"key":"key2025041114531997300_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103819","article-title":"Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism","volume":"314","year":"2022","journal-title":"Artificial Intelligence"},{"year":"2020","article-title":"The quantum alternating operator ansatz on maximum k-vertex cover","key":"key2025041114531997300_ref015"},{"key":"key2025041114531997300_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.118919","article-title":"A metaheuristic algorithm for vertex cover based link monitoring and backbone formation in wireless ad hoc networks","volume":"213","year":"2023","journal-title":"Expert Systems with Applications"},{"year":"2012","first-page":"295","article-title":"Efficient algorithms for the max k-vertex cover problem","key":"key2025041114531997300_ref017"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","key":"key2025041114531997300_ref018"},{"issue":"1","key":"key2025041114531997300_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2021.104344","article-title":"Peavc: an improved minimum vertex cover solver for massive sparse graphs","volume":"104","year":"2021","journal-title":"Engineering Applications of Artificial Intelligence"},{"issue":"2","key":"key2025041114531997300_ref020","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/s0377-2217(02)00330-2","article-title":"On approximation of max-vertex-cover","volume":"143","year":"2002","journal-title":"European Journal of Operational Research"},{"doi-asserted-by":"crossref","unstructured":"Hasan, M., Islam, R. and Mugdha, A.G. (2022), \u201cChemical reaction optimization (cro) for maximum clique problem\u201d, in Modeling, Simulation and Optimization, Springer, pp.\u00a085-96.","key":"key2025041114531997300_ref021","DOI":"10.1007\/978-981-19-0836-1_7"},{"issue":"6","key":"key2025041114531997300_ref022","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1002\/(sici)1520-6750(199809)45:6<615::aid-nav5>3.3.co;2-3","article-title":"Analysis of the greedy approach in problems of maximum k-coverage","volume":"45","year":"1998","journal-title":"Naval Research Logistics"},{"volume-title":"Combinatorial Data Analysis: Optimization by Dynamic Programming","year":"2001","key":"key2025041114531997300_ref023"},{"year":"2021","article-title":"On the design and anytime performance of indicator-based branch and bound for multi-objective combinatorial optimization","key":"key2025041114531997300_ref024"},{"volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993","year":"1996","key":"key2025041114531997300_ref025"},{"key":"key2025041114531997300_ref026","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1145\/3556223.3556235","article-title":"The performance of a local search based on vertex coloring for the maximum clique problem","year":"2022"},{"doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972), \u201cReducibility among combinatorial problems\u201d, in Complexity of Computer Computations, Springer, pp.\u00a085-103.","key":"key2025041114531997300_ref027","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"18","key":"key2025041114531997300_ref028","doi-asserted-by":"publisher","first-page":"15513","DOI":"10.1007\/s00521-022-07262-w","article-title":"A hybrid algorithm based on modified chemical reaction optimization and best-first search algorithm for solving minimum vertex cover problem","volume":"34","year":"2022","journal-title":"Neural Computing and Applications"},{"unstructured":"Kotecha, K. and Gambhava, N. (2003), \u201cA hybrid genetic algorithm for minimum vertex cover problem\u201d, in IICAI, pp.\u00a0904-913.","key":"key2025041114531997300_ref029"},{"key":"key2025041114531997300_ref030","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1016\/j.ins.2016.08.053","article-title":"An efficient local search framework for the minimum weighted vertex cover problem","volume":"372","year":"2016","journal-title":"Information Sciences"},{"key":"key2025041114531997300_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2022.109619","article-title":"A restart local search algorithm with relaxed configuration checking strategy for the minimum k-dominating set problem","volume":"254","year":"2022","journal-title":"Knowledge-Based Systems"},{"issue":"1","key":"key2025041114531997300_ref032","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1108\/ajeb-11-2021-0131","article-title":"A novel approach for candlestick technical analysis using acombination of the support vectormachine and particle swarm optimization","volume":"7","year":"2022","journal-title":"Asian Journal of Economics and Banking"},{"issue":"4","key":"key2025041114531997300_ref033","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1108\/emjb-02-2022-0034","article-title":"Develop an integrated candlestick technical analysis model using meta-heuristic algorithms","volume":"19","year":"2023","journal-title":"EuroMed Journal of Business"},{"issue":"1","key":"key2025041114531997300_ref034","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s12597-022-00608-x","article-title":"A developed stock price forecasting model using support vector machine combined with metaheuristic algorithms","volume":"60","year":"2023","journal-title":"Opsearch: Journal of the Operational Research Society of India"},{"issue":"4","key":"key2025041114531997300_ref035","doi-asserted-by":"publisher","first-page":"5659","DOI":"10.1002\/ijfe.2086","article-title":"A comparison on particle swarm optimization and genetic algorithm performances in deriving the efficient Frontier of stocks portfolios based on a mean-lower partial moment model","volume":"26","year":"2020","journal-title":"International Journal of Finance and Economics"},{"year":"2018","journal-title":"arXiv preprint arXiv:1810.03792","article-title":"A note on max k-vertex cover: faster fpt-as, smaller approximate kernel and improved approximation","key":"key2025041114531997300_ref036"},{"issue":"14","key":"key2025041114531997300_ref037","doi-asserted-by":"publisher","first-page":"6449","DOI":"10.3390\/app11146449","article-title":"Combinatorial optimization problems and metaheuristics: review, challenges, design, and development","volume":"11","year":"2021","journal-title":"Applied Sciences"},{"issue":"4","key":"key2025041114531997300_ref038","first-page":"510","article-title":"An approximation algorithm for facility location on paths, trees and cycles","volume":"32","year":"2002","journal-title":"Algorithmica"},{"year":"2007","first-page":"412","article-title":"A stochastic local search approach to vertex cover","key":"key2025041114531997300_ref039"},{"issue":"1-4","key":"key2025041114531997300_ref040","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1023\/b:anor.0000039523.95673.33","article-title":"An ant colony optimization algorithm for the minimum weight vertex cover problem","volume":"131","year":"2004","journal-title":"Annals of Operations Research"},{"key":"key2025041114531997300_ref041","first-page":"94","article-title":"A cut-plane algorithm for nonsmooth convex programming and its applications in combinatorial optimizatorial problems","volume":"14","year":"2001","journal-title":"Mathematica Applicata"},{"year":"2019","journal-title":"arXiv preprint arXiv:1903.05948","article-title":"An exact algorithm for minimum weight vertex cover problem in large graphs","key":"key2025041114531997300_ref042"},{"key":"key2025041114531997300_ref043","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.103230","article-title":"Sccwalk: an efficient local search algorithm and its improvements for maximum weight clique problem","volume":"280","year":"2020","journal-title":"Artificial Intelligence"},{"key":"key2025041114531997300_ref044","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","article-title":"Exact algorithms for maximum independent set","volume":"255","year":"2017","journal-title":"Information and Computation"},{"volume-title":"A Simple Model to Generate Hard Satisfiable Instances","year":"2005","key":"key2025041114531997300_ref045"},{"issue":"18","key":"key2025041114531997300_ref046","doi-asserted-by":"publisher","first-page":"7831","DOI":"10.3390\/s23187831","article-title":"Tivc: an efficient local search algorithm for minimum vertex cover in large graphs","volume":"23","year":"2023","journal-title":"Sensors"},{"key":"key2025041114531997300_ref047","first-page":"1","article-title":"Bi-objective optimization model and algorithm for urban road network planning","volume":"103","year":"2019","journal-title":"Transportation Research Part C: Emerging Technologies"}],"container-title":["Data Technologies and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/DTA-11-2023-0788\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/DTA-11-2023-0788\/full\/html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T23:15:29Z","timestamp":1753398929000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.emerald.com\/dta\/article\/59\/2\/362-392\/1246539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,12]]},"references-count":47,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2,12]]},"published-print":{"date-parts":[[2025,4,11]]}},"alternative-id":["10.1108\/DTA-11-2023-0788"],"URL":"https:\/\/doi.org\/10.1108\/dta-11-2023-0788","relation":{},"ISSN":["2514-9288","2514-9318"],"issn-type":[{"type":"print","value":"2514-9288"},{"type":"electronic","value":"2514-9318"}],"subject":[],"published":{"date-parts":[[2025,2,12]]}}}