Directed Feedback Vertex Set is Fixed-Parameter Tractable

Simple item page
dc.creatorRazgon, Igor
dc.creatorO'Sullivan, Barry
dc.date2007-07-02
dc.date.accessioned2026-07-07T08:13:35Z
dc.date.available2026-07-07T08:13:35Z
dc.descriptionWe resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose an algorithm which solves this problem in $O(8^kk!*poly(n))$.
dc.description14 pages
dc.identifierhttps://arxiv.org/abs/0707.0282
dc.identifierhttp://arxiv.org/abs/0707.0282
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/132817
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleDirected Feedback Vertex Set is Fixed-Parameter Tractable
dc.typetext

Files

Collections

arXiv