Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Linear Kernels for Outbranching Problems in Sparse Digraphs

Uproszczony widok
dc.abstract.enIn the k-Leaf Out-Branching and k-Internal Out-Branching problems we are given a directed graph D with a designated root r and a nonnegative integer k. The question is whether there exists an outbranching rooted at r that has at least k leaves, or at least k internal vertices, respectively. Both these problems have been studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with O(k2) vertices are known on general graphs. In this work we show that k-Leaf Out-Branching admits a kernel with O(k) vertices on H-minor-free graphs, for any fixed family of graphs H, whereas k-Internal Out-Branching admits a kernel with O(k) vertices on any graph class of bounded expansion.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorSocała, Arkadiusz
dc.contributor.authorKowalik, Łukasz
dc.contributor.authorBonamy, Marthe
dc.date.accessioned2024-01-25T05:11:38Z
dc.date.available2024-01-25T05:11:38Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.number1
dc.description.volume79
dc.identifier.doi10.1007/S00453-016-0244-6
dc.identifier.issn0178-4617
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/111287
dc.identifier.weblinkhttps://link.springer.com/article/10.1007%2Fs00453-016-0244-6
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofAlgorithmica
dc.relation.pages159–188
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enKernelization
dc.subject.enOutbranching
dc.subject.enSparse graph
dc.subject.enBounded expansion
dc.subject.enH-minor-free graphs
dc.titleLinear Kernels for Outbranching Problems in Sparse Digraphs
dc.typeJournalArticle
dspace.entity.typePublication