K-distinct branchings admits a polynomial kernel

DOI10.4230/LIPICS.ESA.2021.11MaRDI QIDQ6075895zbMATH OpenOpenAlexFDO

Authors Jørgen Bang-Jensen, Kristine Vitting Klinkby, Saket Saurabh

Publication date 20 September 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2021/14592/pdf/LIPIcs-ESA-2021-11.pdf/

zbMATH Keywords

digraphsin-branchingout-branchingpolynomial kernel

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• k-distinct in- and out-branchings in digraphs
• \(k\)-distinct in- and out-branchings in digraphs
• Parameterized algorithms for non-separating trees and branchings in digraphs
• Kernel(s) for problems with no kernel
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited in

(3)

• FPT algorithms for packing k-safe spanning rooted sub(di)graphs
• Determinantal sieving
• Max-distance sparsification for diversification and clustering

This page was built for publication: K-distinct branchings admits a polynomial kernel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075895)