Inhalt des Dokuments
Preprint 19-2008
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems
- Authors
- Paul Bonsma and Frederic Dorn
- Publication
- submitted
- Classification
-
not available
- Keywords
-
spanning tree, max leaf, directed graph, fixed parameter tractable
- Abstract
-
An out-tree T of a directed graph D is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By l(D) and ls(D) we denote the maximum number of leaves over all out-trees and out-branchings of D, respectively.We give fixed parameter tractable algorithms for deciding whether ls(D)>=k and whether l(D)>=k for a digraph D on n vertices, both with time complexity 2O(k log k) nO(1). This improves on previous algorithms with complexity 2O(k^3 log k) nO(1) and 2O(k log^2 k) nO(1), respectively.To obtain the complexity bound in the case of out-branchings, we prove that when all arcs of D are part of at least one out-branching, ls(D)>=l(D)/3. The second bound we prove in this paper states that for strongly connected digraphs D with minimum in-degree 3, ls(D)>= Θ (n1/2), where previously ls(D)>= Θ (n1/3) was the best known bound. This bound is tight, and also holds for the larger class of digraphs with minimum in-degree 3 in which every arc is part of at least one out-branching.Created on May 07 2008
- Source
- Download as [PDF]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe