DC FieldValueLanguage
dc.contributor.authorGöke, Alexander-
dc.contributor.authorMarx, Dániel-
dc.contributor.authorMnich, Matthias-
dc.date.accessioned2020-01-28T09:15:30Z-
dc.date.available2020-01-28T09:15:30Z-
dc.date.issued2019-
dc.identifier.citation11th International Conference on Algorithms and Complexity (CIAC 2019)de_DE
dc.identifier.isbn978-303017401-9de_DE
dc.identifier.issn0302-9743de_DE
dc.identifier.urihttp://hdl.handle.net/11420/4604-
dc.description.abstractThe 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.en
dc.language.isoende_DE
dc.relation.ispartofLecture notes in computer sciencede_DE
dc.titleParameterized Algorithms for generalizations of directed feedback vertex setde_DE
dc.typeinProceedingsde_DE
dc.type.dinicontributionToPeriodical-
dcterms.DCMITypeText-
tuhh.abstract.englishThe 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.de_DE
tuhh.publisher.doi10.1007/978-3-030-17402-6_21-
tuhh.type.opusInProceedings (Aufsatz / Paper einer Konferenz etc.)-
dc.type.drivercontributionToPeriodical-
dc.type.casraiConference Paper-
tuhh.container.volume11485 LNCSde_DE
tuhh.container.startpage249de_DE
tuhh.container.endpage261de_DE
dc.relation.conference11th International Conference on Algorithms and Complexity (CIAC 2019)de_DE
item.creatorGNDGöke, Alexander-
item.creatorGNDMarx, Dániel-
item.creatorGNDMnich, Matthias-
item.languageiso639-1en-
item.creatorOrcidGöke, Alexander-
item.creatorOrcidMarx, Dániel-
item.creatorOrcidMnich, Matthias-
item.cerifentitytypePublications-
item.openairetypeinProceedings-
item.grantfulltextnone-
item.mappedtypeinProceedings-
item.openairecristypehttp://purl.org/coar/resource_type/c_5794-
item.fulltextNo Fulltext-
crisitem.author.deptAlgorithmen und Komplexität E-11-
crisitem.author.deptAlgorithmen und Komplexität E-11-
crisitem.author.orcid0000-0002-4721-5354-
Appears in Collections:Publications without fulltext
Show simple item record

Page view(s)

102
Last Week
0
Last month
5
checked on May 6, 2021

Google ScholarTM

Check

Add Files to Item

Note about this record

Cite this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.