In:
ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 6, No. 3 ( 2010-06), p. 1-18
Abstract:
We present an O (√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.
Type of Medium:
Online Resource
ISSN:
1549-6325
,
1549-6333
DOI:
10.1145/1798596.1798599
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2010
detail.hit.zdb_id:
2198259-4
Permalink