An efficient polynomial-time approximation scheme for Steiner forest in planar graphs

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.

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

{"_id":"HZuG8JRFugwS98ZEY","bibbaseid":"eisenstat-klein-mathieu-anefficientpolynomialtimeapproximationschemeforsteinerforestinplanargraphs-2012","downloads":0,"creationDate":"2016-12-19T20:50:58.529Z","title":"An efficient polynomial-time approximation scheme for Steiner forest in planar graphs","author_short":["Eisenstat, D.","Klein, P.","Mathieu, C."],"year":2012,"bibtype":"inproceedings","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"inproceedings","type":"inproceedings","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":[{"propositions":[],"lastnames":["Eisenstat"],"firstnames":["David"],"suffixes":[]},{"propositions":[],"lastnames":["Klein"],"firstnames":["Philip"],"suffixes":[]},{"propositions":[],"lastnames":["Mathieu"],"firstnames":["Claire"],"suffixes":[]}],"year":"2012","pages":"626--638","bibtex":"@inproceedings{eisenstat_efficient_2012,\n\tseries = {{SODA} '12},\n\ttitle = {An efficient polynomial-time approximation scheme for {Steiner} forest in planar graphs},\n\turl = {http://dl.acm.org/citation.cfm?id=2095116.2095169},\n\tabstract = {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.},\n\turldate = {2012-05-04TZ},\n\tbooktitle = {Proceedings of the {Twenty}-{Third} {Annual} {ACM}-{SIAM} {Symposium} on {Discrete} {Algorithms}},\n\tpublisher = {SIAM},\n\tauthor = {Eisenstat, David and Klein, Philip and Mathieu, Claire},\n\tyear = {2012},\n\tpages = {626--638}\n}\n\n","author_short":["Eisenstat, D.","Klein, P.","Mathieu, C."],"key":"eisenstat_efficient_2012","id":"eisenstat_efficient_2012","bibbaseid":"eisenstat-klein-mathieu-anefficientpolynomialtimeapproximationschemeforsteinerforestinplanargraphs-2012","role":"author","urls":{"Paper":"http://dl.acm.org/citation.cfm?id=2095116.2095169"},"downloads":0,"html":""},"search_terms":["efficient","polynomial","time","approximation","scheme","steiner","forest","planar","graphs","eisenstat","klein","mathieu"],"keywords":[],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}