Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners |
| |
Authors: | Yefim Dinitz Michael Elkin Shay Solomon |
| |
Institution: | 1. Department of Computer Science, Ben-Gurion University of the Negev, POB 653, Beer-Sheva, 84105, Israel
|
| |
Abstract: | We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O(k) and weight w(T)=O(k⋅n
1/k
)⋅w(MST(M)), and a spanning tree T′ with weight w(T′)=O(k)⋅w(MST(M)) and unweighted diameter O(k⋅n
1/k
). These trees also achieve an optimal maximum degree. Furthermore, we demonstrate that these trees can be constructed efficiently. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|