An efficient local search for the feedback vertex set problem
type: Item
instance of: scholarly article
title: An efficient local search for the feedback vertex set problem
zbMATH Open document ID: 1461.90128
author: Ansheng Ye
author: Xiaoqing Zhou
author: Zehui Shao
author: Zhi-Qiang Zhang
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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 DIMACS benchmarks.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 7042185
zbMATH Keywords: feedback vertex set
zbMATH Keywords: local search
zbMATH Keywords: variable depth search
zbMATH Keywords: heuristic
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6040726
OpenAlex ID: W2078622513
cites work: Q4293112
cites work: Reducibility among Combinatorial Problems
cites work: An effective local search for the maximum clique problem
cites work: Tabu Search—Part I
cites work: Tabu Search—Part II
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: Q4495203
cites work: Variable neighborhood search: Principles and applications
cites work: Variable neighborhood search
cites work: Reactive local search for the maximum clique problem
cites work: Variable neighborhood search for the maximum clique
cites work: Solving the maximum clique problem using a tabu search approach
cites work: A graph coloring heuristic using partial solutions and a reactive tabu scheme
cites work: Phased local search for the maximum clique problem
cites work: Chained Lin-Kernighan for large traveling salesman problems
cites work: Q4038710
cites work: Q5321485
cites work: Optimization by Simulated Annealing
DOI: 10.3390/A6040726
description: scientific article; zbMATH DE number 7042185