Advanced

An Approximation Algorithm for Directed Shallow Steiner Trees

Lingas, Andrzej LU (2012) 3rd International Conference on Information and Communication Systems (ICICS) In Proceedings of the 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
in
Proceedings of the 3rd International Conference on Information and Communication Systems (ICICS)
pages
1 - 1
publisher
ACM
conference name
3rd International Conference on Information and Communication Systems (ICICS)
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
2013-06-25 15:25:43
date last changed
2016-10-13 04:39:49
@misc{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},
  isbn         = {978-1-4503-1327-8},
  keyword      = {Directed steiner tree,approximation algorithms,time complexity},
  language     = {eng},
  pages        = {1--1},
  publisher    = {ARRAY(0x9863e48)},
  series       = {Proceedings of the 3rd International Conference on Information and Communication Systems (ICICS)},
  title        = {An Approximation Algorithm for Directed Shallow Steiner Trees},
  url          = {http://dx.doi.org/10.1145/2222444.2222445},
  year         = {2012},
}