An Approximation Algorithm for Directed Shallow Steiner Trees
Författare
Summary, in English
We show that the problem of constructing a minimum directed Steiner tree of depth O(log(d)n) in a directed graph of maximum outdegree d admits an expO(root logn)-approximation in polynomial time.
Avdelning/ar
- Computer Science
Publiceringsår
2012
Språk
Engelska
Sidor
1-1
Publikation/Tidskrift/Serie
Proceedings of the 3rd International Conference on Information and Communication Systems (ICICS)
Dokumenttyp
Konferensbidrag
Förlag
Association for Computing Machinery (ACM)
Ämne
- Computer Science
Nyckelord
- Directed steiner tree
- approximation algorithms
- time complexity
Conference name
3rd International Conference on Information and Communication Systems (ICICS)
Conference date
2012-04-03 - 2012-04-05
Conference place
Irbid, Jordan
Status
Published
ISBN/ISSN/Övrigt
- ISBN: 978-1-4503-1327-8