Joint with Pankaj Agarwal & Yusu Wang
In Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 670-671. 2005
Downloads: PDF
Abstract: Given a one-dimensional graph $G$ such that any two consecutive nodes are unit distance away, and such that the minimum number of links between any two nodes (the diameter of $G$) is $O(\log n)$, we prove an $\Omega(n \log n / \log \log n)$ lower bound on the sum of lengths of all the edges (i.e., the weight of $G$). The problem is a variant of the widely studied partial sum problem. This in turn provides a lower bound on Euclidean spanner graphs with small diameter and low weight, showing that a previous upper bound is almost tight.
Back to publications