An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. Eisenstat, D., Klein, P., & Mathieu, C. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, of SODA '12, pages 626--638, 2012. SIAM.
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs [link]Paper  abstract   bibtex   
We give an O(n log3 n) approximation scheme for Steiner forest in planar graphs, improving on the previous approximation scheme for this problem, which runs in O(nf(ε)) time.
@inproceedings{eisenstat_efficient_2012,
	series = {{SODA} '12},
	title = {An efficient polynomial-time approximation scheme for {Steiner} forest in planar graphs},
	url = {http://dl.acm.org/citation.cfm?id=2095116.2095169},
	abstract = {We give an O(n log3 n) approximation scheme for Steiner forest in planar graphs, improving on the previous approximation scheme for this problem, which runs in O(nf(ε)) time.},
	urldate = {2012-05-04TZ},
	booktitle = {Proceedings of the {Twenty}-{Third} {Annual} {ACM}-{SIAM} {Symposium} on {Discrete} {Algorithms}},
	publisher = {SIAM},
	author = {Eisenstat, David and Klein, Philip and Mathieu, Claire},
	year = {2012},
	pages = {626--638}
}
Downloads: 0