Paper Info
Title
Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs
Abstract
We consider the problem Maximum Leaf Spanning Tree (MLST) on digraphs, which is defined as follows. Given a digraph G, find a directed spanning tree of G that maximizes the number of leaves. MLST is NP-hard. Existing approximation algorithms for MLST have ratios of O(√{OPT}) and 92. We focus on the special case of acyclic digraphs and propose two linear-time approximation algorithms; one with ratio 4 that uses a result of Daligault and Thomassé and one with ratio 2 based on a 3-approximation algorithm of Lu and Ravi for the undirected version of the problem. We complement these positive results by observing that MLST is MaxSNP-hard on acyclic digraphs. Hence, this special case does not admit a PTAS (unless P = NP.
Year
DOI
Venue
2011
10.1007/978-3-642-29116-6_7
WAOA
Keywords
Field
DocType
special case,3-approximation algorithm,tree problem,undirected version,maximum leaf,positive result,linear-time approximation algorithm,problem maximum leaf spanning,acyclic digraph,approximation algorithm,digraph g
Discrete mathematics,Approximation algorithm,Combinatorics,Mathematical optimization,Connected dominating set,Spanning tree,Mathematics,Digraph,Special case
Conference
Citations 
PageRank 
References 
2
0.37
16
Authors
3
Name
Order
Citations
PageRank
Nadine Schwartges120.37
Joachim Spoerhase211214.12
Alexander Wolff322222.66