Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
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}},
}