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

DOI10.1016/j.dam.2023.11.026arXiv2105.01582MaRDI QIDQ6153458

Dieter Rautenbach, Ignasi Sau, Florian Hoersch, Stéphane Bessy, Ana Karolinna Maia

Publication date: 14 February 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.01582

zbMATH Keywords

digraphsarborescencesfixed-parameter tractabilityparameterized complexitypacking problemsbranching flowssafe spanning trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of finding arc-disjoint branching flows
• Which problems have strongly exponential complexity?
• Balanced branchings in digraphs
• (Arc-)disjoint flows in networks
• Connectivity in digraphs
• On the Problem of Decomposing a Graph into n Connected Factors
• Parameterized Algorithms
• Digraphs
• On the complexity of \(k\)-SAT

This page was built for publication: FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs