An Approximation Algorithm for Directed Shallow Steiner Trees
Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding
Abstract
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.
Detaljer
| Författare | |
|---|---|
| Forskningsområden | Ämnesklassifikation (UKÄ) – OBLIGATORISK
Nyckelord |
| Originalspråk | engelska |
|---|---|
| Titel på värdpublikation | Proceedings of the 3rd International Conference on Information and Communication Systems (ICICS) |
| Förlag | Association for Computing Machinery (ACM) |
| Sidor | 1 |
| ISBN (tryckt) | 978-1-4503-1327-8 |
| Status | Published - 2012 |
| Publikationskategori | Forskning |
| Peer review utförd | Ja |
| Evenemang | 3rd International Conference on Information and Communication Systems (ICICS) - Irbid, Jordan Varaktighet: 2012 apr 3 → 2012 apr 5 |
Konferens
| Konferens | 3rd International Conference on Information and Communication Systems (ICICS) |
|---|---|
| Land | Jordan |
| Ort | Irbid |
| Period | 2012/04/03 → 2012/04/05 |
