English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput.Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] aboutfinding disjoint "balanced" spanning rooted substructures in graphs anddigraphs, which generalize classic packing problems. Namely, given a positiveinteger $k$, a digraph $D=(V,A)$, and a root $r \in V$, we consider the problemof finding two arc-disjoint $k$-safe spanning $r$-arborescences and the problemof finding two arc-disjoint $(r,k)$-flow branchings. We show that both theseproblems are FPT with parameter $k$, improving on existing XP algorithms. Thelatter of these results answers a question of Bang-Jensen, Havet, and Yeo[Discret. Appl. Math. 2016]. Further, given an integer $k$, a graph $G=(V,E)$,and $r \in V$, we consider the problem of finding two arc-disjoint $(r,k)$-safespanning trees. We show that this problem is also FPT with parameter $k$, againimproving on a previous XP algorithm. Our main technical contribution is toprove that the existence of such spanning substructures is equivalent to theexistence of substructures with size and maximum (out-)degree both bounded by a(linear or quadratic) function of $k$, which may be of independent interest.

FPT algorithms for packing $k$-safe spanning rooted sub(di)graphs