An Approximation Algorithm for Directed Shallow Steiner Trees

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper 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

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikationProceedings of the 3rd International Conference on Information and Communication Systems (ICICS)
FörlagAssociation for Computing Machinery (ACM)
Sidor1
ISBN (tryckt)978-1-4503-1327-8
StatusPublished - 2012
PublikationskategoriForskning
Peer review utfördJa
Evenemang3rd International Conference on Information and Communication Systems (ICICS) - Irbid, Jordan
Varaktighet: 2012 apr 32012 apr 5

Konferens

Konferens3rd International Conference on Information and Communication Systems (ICICS)
LandJordan
OrtIrbid
Period2012/04/032012/04/05