In the Rooted k-Leaf Outbranching Problem, a digraph G = (V,E), a vertex r of G, and an integer k are given, and the goal is to find an r-rooted spanning outtree of G with ≥ k leaves (a tree with vertex set V, all edges directed away from r, and ≥ k leaves). We present a linear-time algorithm to compute a problem kernel with O(k~6) vertices and O(k~7) edges for the Rooted k-Leaf Outbranching Problem. By combining the new result with a result of Daligault and Thomasse [IWPEC 2009], a kernel with a quadratic number of vertices and edges can be found on n-vertex m-edge digraphs in time O(n + m + k~(14)).
展开▼
机译：在有根k叶分支问题中，给出了有向图G =（V，E），G的顶点r和整数k，目的是找到具有≥k个叶子的G的r根跨越树（一棵树的顶点集为V，所有边都背向r，且≥k离开）。我们提出了一个线性时间算法来计算有根K-叶分支问题的O（k〜6）个顶点和O（k〜7）个边的问题核。通过将新结果与Daligault和Thomasse的结果相结合[IWPEC 2009]，可以在时间O（n + m + k〜（14 ））。
展开▼
