A linear-time kernelization for the Rooted k-Leaf Outbranching Problem
A linear-time kernelization for the Rooted k-Leaf Outbranching Problem
复制标题
有根 k 叶分支问题的线性时间核化
DOI：
10.1016/j.dam.2015.04.028
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Frank Kammer
中科院分区：
文献类型：
--
作者：
Frank Kammer
摘要在有根k-叶分支问题中，给出了一个有向图G=(V，E)，G的一个顶点r和一个整数k，目标是找到G的一棵有≥k个叶的r-根生成外树(G的一个子树，其顶点集V，所有边都指向远离r，≥k个叶)。对于有根k-Leaf分支问题，我们提出了一个线性时间算法，该算法计算一个具有O(K6)个顶点和O(K7)条边的问题核。将新结果与Dregault和Thomassé(2009)的结果相结合，可以在O(n+m+k14)时间内找到n-顶点m-边有向图的一个具有二次点数和边数的核。
Abstract 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 subtree of G with vertex set V, all edges directed away from r, and≥ k leaves). We present a linear-time algorithm that computes 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 Thomassé (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).
流式内核化
DOI：
10.1007/978-3-662-44465-8_24
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
Stefan Fafianie;Stefan Kratsch
通讯作者：
Stefan Kratsch
影响因子：
1.1
作者：
René van Bevern
通讯作者：
René van Bevern