Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235469] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Wang, Y; Yin, P, Lower bound for sparse Euclidean spanners, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2005), pp. 670-671
    (last updated on 2018/11/18)

    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 Ω(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 the upper bound from [1] is almost tight.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320