Advanced

An Approximation Algorithm for Directed Shallow Steiner Trees

Lingas, Andrzej LU (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:
author
organization
publishing date
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
2020-01-12 21:12:39
@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},
  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},
}