2008/10/27 by Jean Daligault, Gregory Gutin, Daligault, Jean +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.0810.4946
openalex publication_date 2008/10/27 · arxiv created 2009/08/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A subgraph T of a digraph D is an \em out-branching if T is an oriented spanning tree with only one vertex of in-degree zero (called the \em root). The vertices of T of out-degree zero are \em leaves. In the \sc Directed k-Leaf Problem, we are given a digraph D and an integral parameter k, and we are to decide whether D has an out-branching with at least k leaves. Recently, Kneis et al. (2008) obtained an algorithm for the problem of running time 4k⋅ nO(1). We describe a new algorithm for the problem of running time 3.72k⋅ nO(1). In \sc Rooted Directed k-Leaf Problem, apart from D and k, we are given a vertex r of D and we are to decide whether D has an out-branching rooted at r with at least k leaves. Very recently, Fernau et al. (2008) found an O(k3)-size kernel for \sc Rooted Directed k-Leaf. In this paper, we obtain an O(k) kernel for \sc Rooted Directed k-Leaf restricted to acyclic digraphs.