Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem

被引：0

作者：

Fleischer, Rudolf ^{[1
]}

Wu, Xi

Yuan, Liwei

机构：

[1] Fudan Univ, Shanghai 200433, Peoples R China

来源：

ALGORITHMS - ESA 2009, PROCEEDINGS | 2009年 / 5757卷

关键词：

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We evaluate the performance of FPT algorithms for the directed feedback vertex set problem (DFVS). We propose several new data reduction rules for DFVS. which can significantly reduce the search space. We also propose various heuristics to accelerate the EPT search. Finally, we demonstrate that DFVS is not more helpful for deadlock recovery (with mutex locks) than simple cycle detection.

引用

页码：611 / +

页数：2

共 17 条

[1]

Bodlaender HL, 2008, LECT NOTES COMPUT SC, V5018, P160, DOI 10.1007/978-3-540-79723-4_16

[2] ON LINEAR TIME MINOR TESTS WITH DEPTH-1ST SEARCH [J].