An Approximation Algorithm for Directed Shallow Steiner Trees
(2012) 3rd International Conference on Information and Communication Systems (ICICS) p.1-1- 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3821385
- author
- Lingas, Andrzej LU
- organization
- publishing date
- 2012
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Directed steiner tree, approximation algorithms, time complexity
- host publication
- Proceedings of the 3rd International Conference on Information and Communication Systems (ICICS)
- pages
- 1 - 1
- publisher
- Association for Computing Machinery (ACM)
- conference name
- 3rd International Conference on Information and Communication Systems (ICICS)
- conference location
- Irbid, Jordan
- conference dates
- 2012-04-03 - 2012-04-05
- external identifiers
-
- wos:000318625800001
- scopus:84862700840
- ISBN
- 978-1-4503-1327-8
- DOI
- 10.1145/2222444.2222445
- language
- English
- LU publication?
- yes
- id
- fcb86c18-dcd8-4c4d-a734-cccf0da3cec0 (old id 3821385)
- date added to LUP
- 2016-04-04 10:23:50
- date last changed
- 2022-01-29 20:15:22
@inproceedings{fcb86c18-dcd8-4c4d-a734-cccf0da3cec0, 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.}}, author = {{Lingas, Andrzej}}, booktitle = {{Proceedings of the 3rd International Conference on Information and Communication Systems (ICICS)}}, isbn = {{978-1-4503-1327-8}}, keywords = {{Directed steiner tree; approximation algorithms; time complexity}}, language = {{eng}}, pages = {{1--1}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{An Approximation Algorithm for Directed Shallow Steiner Trees}}, url = {{http://dx.doi.org/10.1145/2222444.2222445}}, doi = {{10.1145/2222444.2222445}}, year = {{2012}}, }