@inproceedings{1c67c7f5276b4d2d9e0f98ea996e48eb,
title = "Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces",
abstract = "We give an algorithm that computes a (1+?)-approximate Steiner forest in near-linear time n · 2(1/?)O(ddim2) (loglogn)2, where ddim is the doubling dimension of the metric space. This improves upon the best previous result due to Chan et al. (SIAM J. Comput. 4 (2018)), who gave a runtime of about n2O(ddim) · 2(ddim/?)O(ddim) ?logn. For Steiner tree our methods achieve an even better runtime n (logn)(1/?)O(ddim2).",
keywords = "Steiner forest, banyans, doubling dimension",
author = "Yair Bartal and Gottlieb, \{Lee Ad\}",
note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 ; Conference date: 21-06-2021 Through 25-06-2021",
year = "2021",
month = jun,
day = "15",
doi = "10.1145/3406325.3451063",
language = "אנגלית",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "1028--1041",
editor = "Samir Khuller and Williams, \{Virginia Vassilevska\}",
booktitle = "STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing",
}