The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

An Approximation Algorithm for Directed Shallow Steiner Trees

På svenska

Author

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.

Department/s

  • Computer Science

Publishing year

2012

Language

English

Pages

1-1

Publication/Series

Proceedings of the 3rd International Conference on Information and Communication Systems (ICICS)

Document type

Conference paper

Publisher

Association for Computing Machinery (ACM)

Topic

  • Computer Science

Keywords

  • 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/Other

  • ISBN: 978-1-4503-1327-8