Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.3390/a6040726 | ALGORITHMS |
Keywords | Field | DocType |
feedback vertex set, local search, variable depth search, heuristic | Mathematical optimization,Vertex (geometry),Reachability,Vertex cover,Bidirectional search,Local search (optimization),Deadlock prevention algorithms,Feedback arc set,Feedback vertex set,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 4 | 1999-4893 |
Citations | PageRank | References |
1 | 0.35 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhiqiang Zhang | 1 | 1 | 0.35 |
| Ansheng Ye | 2 | 1 | 0.35 |
| Xiaoqing Zhou | 3 | 1 | 0.35 |
| Zehui Shao | 4 | 119 | 30.98 |