|Publisher DOI:||10.1007/978-3-030-17402-6_21||Title:||Parameterized Algorithms for generalizations of directed feedback vertex set||Language:||English||Authors:||Göke, Alexander
|Issue Date:||2019||Source:||Lecture Notes in Computer Science, 11485 LNCS: 249-261 (2019)||Journal or Series Name:||Lecture notes in computer science||Abstract (english):||The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 -complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a -time algorithm, where. Here we show fixed-parameter tractability of two generalizations of DFVS: Find a smallest vertex set S such that every strong component of has size at most s: we give an algorithm solving this problem in time. Find a smallest vertex set S such that every non-trivial strong component of is 1-out-regular: we give an algorithm solving this problem in time. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.||URI:||http://hdl.handle.net/11420/4604||ISBN:||978-303017401-9||ISSN:||0302-9743||Type:||InProceedings (Aufsatz / Paper einer Konferenz etc.)|
|Appears in Collections:||Publications without fulltext|
Show full item record
checked on Sep 30, 2020
Add Files to Item
Note about this record
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.