An Approximation Algorithm for the Maximum Leaf Spanning Arborescence Problem

作者：Drescher Matthew^*; Vetta Adrian

来源：ACM Transactions on Algorithms, 2010, 6(3): 46.

DOI：10.1145/1798596.1798599

• Algorithms
• Theory
• Approximation Algorithms
• directed graphs
• maximum leaf
• arborescence

We present an O(root OPT)-approximation algorithm for the maximum leaf spanning arborescence problem, where OPT is the number of leaves in an optimal spanning arborescence. The result is based upon an O(1)-approximation algorithm for a special class of directed graphs called willows. Incorporating the method for willow graphs as a subroutine in a local improvement algorithm gives the bound for general directed graphs.

• 出版日期2010-6